
Flipping Edged in Triangulations 


BOUND ON THE DIAMETER G_{T}(P_{n})
What is G_{T}(P_{n})? To review, given a set of points P_{n} we define the graph of triangulations of P_{n, } denoted as G_{T}(P_{n}), to be the the graph such that the vertices are the triangulations of P_{n}, two triangulations being adjacent if one can be obtained from the other by flipping an edge. The following theorem shows that the diameter G_{T}(P_{n}) is sensitive to the number of convex layers.
Helpful Lemmas and TheoremsWe present lemma 6, 7 and 8 for use in the proof of theorem 5. We need the following lemma to present the proof for lemma 7:
Proof of Lemma 6:Suppose uv is a diagonal of the triangulation T and assume, without loss of generality, that the endpoint of each edge e of T intersecting and below uv is a convex vertex of Q.
Let Q_{i,j} be the subpolygon of Q obtained by joining all the triangles of T intersected by v_{i}v_{j}. Let T' be the triangulation induced by T in Q_{i,j. } Let t be the number of edges that v_{i}v_{j }is intersected by; t is greater than or equal to 1. In our next step we will show that by flipping at most 2 edges of T' we can obtain a new triangulation in which v_{i}v_{j }is intersected by t1 edges. Let u_{1},...,u_{m} denote the vertices of Q_{i,j} between v_{i }and v_{j }in the clockwise direction. Let u_{t} be a convex vertex of Q_{i,j} (there is at least one convex vertex otherwise v_{i }and v_{j }would not be visible in Q). If u_{t} is in T' then it is adjacent to exactly one vertex in the set {v_{1+1},...,v_{j1}} and the edge connecting them in T' can be flipped. After flipping the stated edge, the number of edge that intersect v_{i}v_{j }say v_{s1}v_{s} is reduced by 1. Then the edge u_{t}v_{s} intersecting v_{s1}v_{s+1} can be flipped and our result follows. Now, suppose that u_{t} is adjacent to exactly two vertices, say v_{s} and v_{s+1}, in v_{i+1},...,v_{j1}.
Since u_{t} is convex, we can flip u_{t}v_{s+1} and then flip u_{t}v_{s}. The number of edges intersecting v_{i}v_{j} has gone down by one. Our result now follows. Finally suppose that Q has k reflex vertices labeled v_{i1},...,v_{ik }such that i1 <...< ik. For each j = 1,...,k let R_{j} be the shorted polygonal chain containing Q joining v_{j }to v_{j+1}. Let R = R_{1} U ... U R_{k}.
Proof of Lemma 7:We denote the first and second convex layers as C_{1} and C_{2 }respectively. An edge of T can cross C_{2} at most twice. If an edge of T crosses C_{2} twice then the endpoints are in C_{1}. Let r denote the the number of edges that cross C_{2 }twice. First it will be shown that all the r edges can be removed with r flips (clearly r < n). Let uv be an edge of T crossing C_{2 }twice and w be a vertex such that uvw is a triangle of T. Suppose w is not in C_{1} then it can be flipped and a new edge is obtained which crosses C_{2} at most once. If uv does not cross an edge of C_{2} twice then either uw or vw crosses C_{2 }twice and the process is continued until a flippable edge is found. Now we assume that no edge of T crosses C_{2} twice. Then we let for every edge e of C_{2} P_{e} be the polygon formed by the union of all the triangles that cross e. Applying the above lemma to P_{e} we can insert e without creating new crossings with C_{2}. Thus, we now can conclude that C_{2} can be inserted with a linear number of flips.
A polygon Q_{n} is called a spiral polygon if the vertices of Q_{n} can be labeled v_{1},..., v_{s},v_{s+1},...,v_{n} such that v_{1},...,v_{s }are reflex vertices of Q_{n} and v_{s+1},...,v_{n} are convex vertices of Q_{n}. Below is an example of a spiral polygon
Further, we need one more result to assist us in our proof. Suppose that Q_{n} has k reflex vertices: v_{i1},..., v_{ik} such that i1 < ...< ik. For each j=1,...,k let R_{j }be the shortest polygonal chain contained in Q_{n} joining v_{ij} to v_{i(j+1)}, addition mod k. Then let R = R_{1 }U...U R_{k}. Then we have the following lemma.
Main ProofWe are now ready to prove our main theorem... Proof of Theorem 5:Let T and T' be any two triangulations of P_{n}. Using Lemma 6 we can insert the second convex layer of P_{n} into T and T' with O(n) flips obtaining two new triangulations T_{1} and T_{1}'. We denote the first and second convex layers as: C_{1} = {v_{1},..., v_{q}} and C_{2} = {u_{1},...,u_{p}}. Without loss of generality, let u_{1}v_{1} be a vertex which does not cross C_{2}. Retriangulate the polygon between C_{1 }and C_{2} as follows. u1v1 is a proper diagonal and so it can be inserted both in T_{1} and T_{1}' with O(n) flips using lemma 8. This creates Q = v_{1}...v_{q}v_{1}u_{1}u_{p}....u_{2}u_{1}, a spiral polygon. Using Lemma 7 the triangulations induced by T_{1} and T_{1}' in Q can be transformed into each other with O(n) flips. The process is repeated inside C_{2} and k is the number of convex layers so the result is proven true. 
Last Updated
December 2, 2003 