
Flipping Edged in Triangulations 


PRELIMINARIESWhat is a triangulation of a Point Set?Let P = {v_{1},..., v_{n}} be a collection of points on the plane.
A Triangulation of P is a partitioning of the convex hull of P, which we denote as CH(P), into a set of triangles T = {t_{1},...,t_{m}}.
Each triangle of T has a disjoint interior such that the vertices of each triangle t_{1} of T are points of P. Further, the elements of P are called the vertices of T and the edges of the triangles t_{1},...,t_{m} of T are called the edges of T.
The degree of a vertex v, which we denote as d(v) is the number of edges of T that have v as an endpoint. Flipping the edges of a triangulationAn edge of T is flippable if e is contained in the boundary of two triangles t and t' of T and C = tUt' is a convex quadrilateral. We define flipping e to mean the operation of removing e from T and replacing it by the other diagonal of C.
Describing a triangulation using a graphGiven a collection of points P_{n} = {v_{1},..., v_{n}} we define the graph G_{T}(P), the graph of triangulations of P_{n}, to be the graph such that the vertices of G_{T}(P) are the triangulations of P, two triangulations being adjacent if one can be obtained from the other by flipping an edge. Distance between triangulationsGiven two triangulations T' and T'' of P, we can say that they are at distance k if their distance in G_{T}(P) is k. Stated another way, that means there is a set of k triangulations T_{o} = T',...,T_{k }= T'' such that T_{i+1} can be obtained from T_{i} by flipping one edge, for all i = 0,..., k1. We also say that T' can be transformed into T'' be flipping k edges. Triangulations and Edge Flipping of PolygonsTriangulations of polygons, flipping edges in them, and their corresponding graphs of triangulations are defined in an analogous way. Assumptions for proofs and theoremsMake note of the following notations and assumptions! We denote point sets as P_{n} and polygons as Q_{n}. The vertices of Q_{n} are assumed to be labeled in clockwise order and that no three consecutive vertices are collinear.
We denote the graph of a triangulation of a point set P as G_{T}(P) and similarly for a polygon Q, G_{T}(Q). We denote the convex hull of a point set P as CH(P). 
Last Updated
December 2, 2003 