Flipping Edged in Triangulations

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


What is a triangulation of a Point Set?

Let P = {v1,..., vn} be a collection of points on the plane

To the left we have n points in the 2D 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 = {t1,...,tm}.

Shows a triangulation of the above points 


 Each triangle of T has a disjoint interior such that the vertices of each triangle t1 of T are points of P.  Further, the elements of P are called the vertices of T and the edges of the triangles t1,...,tm of T are called the edges of T


Thus each triangle (different colour) has a disjoint interior and the the vertices are the original n points


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 triangulation

An 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 graph

Given a collection of points Pn = {v1,..., vn} we define the graph GT(P), the graph of triangulations of Pn, to be the graph such that the vertices of GT(P) are the triangulations of P, two triangulations being adjacent if one can be obtained from the other by flipping an edge.

Distance between triangulations

Given two triangulations T' and T'' of P, we can say that they are at distance k if their distance in GT(P) is k. Stated another way, that means there is a set of k triangulations To = T',...,Tk = T'' such that Ti+1 can be obtained from Ti by flipping one edge, for all i = 0,..., k-1

We also say that T' can be transformed into T'' be flipping k edges.

Triangulations and Edge Flipping of Polygons

Triangulations of polygons, flipping edges in them, and their corresponding graphs of triangulations are defined in an analogous way.

Assumptions for proofs and theorems

Make note of the following notations and assumptions! 

We denote point sets as Pn and polygons as Qn. The vertices of Qn are assumed to be labeled in clockwise order and that no three consecutive vertices are collinear.

Notice the clockwise labeling of the vertices of polygon on the left!

ABCD are collinear! We are not going to consider polygons of this type!

We denote the graph of a triangulation of a point set P as GT(P) and similarly for a polygon Q, GT(Q).

We denote the convex hull of a point set P as CH(P).


Last Updated December 2, 2003 
By Christina Boucher