
Flipping Edged in Triangulations 


NUMBER OF FLIPPABLE EDGESGiven a triangulation T of a collection P_{n} = {v_{1},...,v_{n}} of n points on the plane, how many edges of T are flippable? The following theorem gives us the result. You can intuitively see the result by trying different triangulations in the applet.
We will come back to the proof of Theorem 1 after investigating the problem further.... The above figure show a triangulation of a point set where only (n2)/4 edges are flippable General Position AssumptionIt is important to note that the general position assumption is necessary since otherwise it is easy to construct a triangulation where no edge can be flipped.
Further notationGiven a triangulation T we can divide the set of edges of T into two subsets:
Clearly all the edges of T contained in the boundary of the convex hull of P_{n} are not flippable. We create an orientation of each edge e in NF(T) as follows:
Consider any vertex v_{i} of T. Let d^{}(v_{i}) be the number of edges of v_{i} in NF(T) oriented from v_{j} to v_{i}. Note that d(v_{i}) is the total number of edges of T incident with v_{i}, whereas d^{}(v_{i}) involves only edges of T in NF(T).
Helpful LemmaWe use the following lemma to prove our main theorem...
Proof of Lemma 2:If v_{i} is in CH(P_{n}) then d^{}(v_{i}) = 1. Next, suppose then that v_{i} is in the interior of CH(P_{n}); then two cases arise: Case 1: d(v_{i}) = 3 in T. In this case, all the edges of T incident with v_{i} are nonflippable and are oriented toward v_{i}. It follows that d^{}(v_{i}) = 3. Case 2: d(v_{i}) > 3 in T. It is obvious that no more than two edges of G can be oriented toward dv_{i} and that if d^{}(v_{i}) = 2, then the two edges oriented toward v_{i} must be consecutive edges incident to v_{i}.
In the Below figured the oriented, nonflippable edges are the dashed lines whereas the flippable edges are solid.
Main TheoremUsing Lemma 2 and the above information we can now go on to prove Theorem 1. Proof of Theorem 1:The proof comes in the following steps: Step 1: Start with initial set of points and find a triangulation of the points.
Step 5: Orient the edges according to Rule 1 and 2. Each of the edges incident to w are contained in NF(T) and we orient them from w to the vertex contained on CH(P_{n}). Next we orient all edges of T in NF(T) according to Rule 1 and Rule 2 above (see below). Notice that with these orientations, d^{}(v_{i}) = 2 for all the elements of P_{n} of CH(P_{n}). The edges oriented using Rule 1 are blue and the edges oriented using rule 2 are in green. Step 6: Remove all the vertices in the set S. Next we remove from T all the elements of S. Notice that we remove exactly 3S edges of T which are not flippable and what remains is a triangulation T' of P_{n}  S + {w}, which by Euler's formula contains 2(P_{n}  S + 1)  4 = 2(n  S)  2 triangles. Any element v_{i} of P_{n}  S + {w} that is not in the convex hull of vertices of P_{n}  S + {w} that have d^{}(v_{i}) = 2. Step 7: Use lemma 2 on the resulting graph of step 6. Using lemma 2 we can associate to every vertex v_{i} of Q in the interior of CH(P_{n}) a triangle t(v_{i}) of T' which is also a triangle in T, bounded by two oriented edges and the triangles t(v_{i}) are all different. To each vertex v_{i} of T' in CH(P_{n}) we can also associate a different triangle of T' among those having w as one of their vertices. Therefore, to each vertex of T' which is not w or a vertex of T' with d^{}(v_{i}) < 2, we associate a different triangle of T' that contains no element of S. Thus, the number of edges of T that can be flipped is minimized when all the vertices v_{i} not in S have d^{}(v_{i}) = 2. We have n  S triangles associated with vertices in Q and as T' has 2n  2S  2 triangles, at most n  S  2 of them contained points of S in T. Using the inequality S ≤ n  S  2 we get: (3n  3)  3S  2(n  S) = n  S  3 ≥ (n  4)/2 which is the number of flippable edges in T.


Analogous Results for PolygonsWe have analogous result of Theorem 1 for polygons.

Last Updated
December 2, 2003 