# Show triangulations can be transformed into each other by edge flip.

Let $\Delta_1$ and $\Delta_2$ be two triangulations of the same point set $P_n$. Show that they can be transformed into each other by edge flips. To define an edge flip, let $pqrs$ be vertices (in clockwise order) of a quadrilateral. If $pr$ is an edge in the triangulation, then $pr$ can be flipped into $qs$.

For convex polygon case, it is easy to show there exists a sequence of edge flip that will increase the number of common edges of two different triangulations. But I am stuck in the general case. Any hint?

• The triangulation of a set of points contains the convex hull of the points, by definition -- see this Wikipedia article. If it didn't, how would you know when to stop? – TonyK Apr 29 '12 at 8:59
• @TonyK Yes the boundary of triangulation of P must be a convex hull. The convex case means the vertices form a convex polygon. The general case can be: $n-k$ points forms the convex hull while $k$ points are inside the convex hull. For example, when $k=1$, we can always flip it so that all vertices are neighbors of that interior point. So, $\Delta_1$ -> $T$ -> $\Delta_2$ by reversing the edge flips that causes $\Delta_2$ to become $T$. – FiniteA Apr 29 '12 at 23:53

Another way to show this is by using the optimization properties of the Delaunay triangulation, which are treated e.g. in this paper (Section 4.2) and this presentation. Call an edge of a triangulation locally Delaunay if it is part of the convex hull or if the circumcircle of neither triangle containing it contains the third vertex of the other triangle containing it. Then any edge that isn't locally Delaunay can be replaced through an edge flip by one that is. Also, if we order the triangulations by forming the vector of vertex angles (all triangulations have the same number of triangles and thus of vertex angles), sorting it in ascending order and using the lexicographical order on these sorted vectors, the edge flips increase the triangulation with respect to this order, since they increase the minimal angle in the triangles containing them. Thus the process must terminate with a triangulation in which all edges are locally Delaunay. This implies the global Delaunay properties, and thus the resulting triangulation is a Delaunay triangulation. Any Delaunay triangulation can be transformed into any other Delaunay triangulation using edge flips in the convex polygons around Voronoi vertices equidistant from more than three points. (Alternatively, slightly perturb the points to bring them into general position to make the Delaunay triangulation unique and thus avoid this special case.) Thus, there is a sequence of edge flips from $\Delta_1$ to a Delaunay triangulation to another Delaunay triangulation and back to $\Delta_2$ (using the inverse of the sequence of edge flips required to turn $\Delta_2$ into a Delaunay triangulation).