Flipping Edges in Triangulations

Home| Preliminaries| Edge Flipping Theorems| Applications| Applet| Glossary| Links| References


This web page describes the method of flipping edges in triangulations of polygons and point sets.  When an edge is flipped in any given triangulation a new triangulation of the same points or polygon is obtained.  The purpose of this page is to be used as an introductory tool to triangulations and edge flipping in triangulations.  

Then given two triangulations an important question arises as to can one triangulation be obtained from another in a series of edge flip operations?  The question as to if one triangulation can be obtained from a given triangulation of points is of considerable interest in such areas as computational geometry, optimization, geometric combinatorics as well as many others...  

Edge flipping, being a natural and simple transformation of a triangulation, is applicable to many areas of computational geometry.  Mesh generation, Delaunay triangulation and many other areas have used the concept of edge flipping.

Our investigation centers around the triangulation and transformation of point sets.  The proofs to some natural results of edge flipping in a triangulation are given and a helpful applet is included to give a hands-on feel for the proofs stated.

To begin we will give some definitions...

Given a triangulation T of a set P of points on the plane, a edge e of T is flippable if it is adjacent to two triangles whose union is a convex quadrilateral C.  By flipping e we mean the operation of removing e from T and replacing it by the other diagonal of C

By this method we obtain a new triangulation T' of P, and we say that T' has been obtained from T by means of a flip.  

   Present to: Prof. Godfried T. Toussaint 308-507A - Computational Geometry -- Web Project    
   Present by: Christina Anne Boucher McGill University     
   cbouch35@cs.mcgill.ca School of Computer Science    
   Fall 2003