|
Flipping Edged in Triangulations |
|
BOUND ON THE DIAMETER GT(Pn)
What is GT(Pn)? To review, given a set of points Pn we define the graph of triangulations of Pn, denoted as GT(Pn), to be the the graph such that the vertices are the triangulations of Pn, two triangulations being adjacent if one can be obtained from the other by flipping an edge. The following theorem shows that the diameter GT(Pn) 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 Qi,j be the subpolygon of Q obtained by joining all the triangles of T intersected by vivj. Let T' be the triangulation induced by T in Qi,j. Let t be the number of edges that vivj 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 vivj is intersected by t-1 edges. Let u1,...,um denote the vertices of Qi,j between vi and vj in the clockwise direction. Let ut be a convex vertex of Qi,j (there is at least one convex vertex otherwise vi and vj would not be visible in Q). If ut is in T' then it is adjacent to exactly one vertex in the set {v1+1,...,vj-1} and the edge connecting them in T' can be flipped. After flipping the stated edge, the number of edge that intersect vivj say vs-1vs is reduced by 1. Then the edge utvs intersecting vs-1vs+1 can be flipped and our result follows. Now, suppose that ut is adjacent to exactly two vertices, say vs and vs+1, in vi+1,...,vj-1.
Since ut is convex, we can flip utvs+1 and then flip utvs. The number of edges intersecting vivj has gone down by one. Our result now follows. Finally suppose that Q has k reflex vertices labeled vi1,...,vik such that i1 <...< ik. For each j = 1,...,k let Rj be the shorted polygonal chain containing Q joining vj to vj+1. Let R = R1 U ... U Rk.
Proof of Lemma 7:We denote the first and second convex layers as C1 and C2 respectively. An edge of T can cross C2 at most twice. If an edge of T crosses C2 twice then the endpoints are in C1. Let r denote the the number of edges that cross C2 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 C2 twice and w be a vertex such that uvw is a triangle of T. Suppose w is not in C1 then it can be flipped and a new edge is obtained which crosses C2 at most once. If uv does not cross an edge of C2 twice then either uw or vw crosses C2 twice and the process is continued until a flippable edge is found. Now we assume that no edge of T crosses C2 twice. Then we let for every edge e of C2 Pe be the polygon formed by the union of all the triangles that cross e. Applying the above lemma to Pe we can insert e without creating new crossings with C2. Thus, we now can conclude that C2 can be inserted with a linear number of flips.
A polygon Qn is called a spiral polygon if the vertices of Qn can be labeled v1,..., vs,vs+1,...,vn such that v1,...,vs are reflex vertices of Qn and vs+1,...,vn are convex vertices of Qn. Below is an example of a spiral polygon
Further, we need one more result to assist us in our proof. Suppose that Qn has k reflex vertices: vi1,..., vik such that i1 < ...< ik. For each j=1,...,k let Rj be the shortest polygonal chain contained in Qn joining vij to vi(j+1), addition mod k. Then let R = R1 U...U Rk. 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 Pn. Using Lemma 6 we can insert the second convex layer of Pn into T and T' with O(n) flips obtaining two new triangulations T1 and T1'. We denote the first and second convex layers as: C1 = {v1,..., vq} and C2 = {u1,...,up}. Without loss of generality, let u1v1 be a vertex which does not cross C2. Re-triangulate the polygon between C1 and C2 as follows. u1v1 is a proper diagonal and so it can be inserted both in T1 and T1' with O(n) flips using lemma 8. This creates Q = v1...vqv1u1up....u2u1, a spiral polygon. Using Lemma 7 the triangulations induced by T1 and T1' in Q can be transformed into each other with O(n) flips. The process is repeated inside C2 and k is the number of convex layers so the result is proven true. |
|
Last Updated
December 2, 2003 |