Flipping Edged in Triangulations

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

# BOUND ON THE DIAMETER GT(Pn)

## Theorem for GT(Pn) for point sets

The diameter of a simple polygon Q is defined as the maximum distance between any two points of Q.  Here we will present a bound on the diameter of the graph of triangulations of Pn, GT(Pn).

The convex layers of a point set are obtained by removing the convex hull (the first layer), finding the convex hull of the remaining points, and repeating until no point is left.

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.

#### Theorem 5:

Let Pn be a collection of n points on the plane, and let k be the number of convex layers in Pn.  Then the diameter of GT(Pn) is O(kn).

We 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:

 Lemma 6: Let uv be a proper diagonal of a triangulation T of a polygon Q.  Then if uv is intersected by t edges of T, uv can be inserted in T using at most 2t flips.

#### 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.

 uv is a proper diagonal

Let Qi,j be the subpolygon of Q obtained by joining all the triangles of T intersected by vivjLet 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.

 Proof of Lemma 6

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.

 Polygon R is in bold.

#### Lemma 7:

Let T any triangulation of Pn. The edges of the second convex layer can be inserted in T using O(n) flips.

#### 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 C1Let 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

#### Lemma 8:

Let Qn be a spiral polygon with k reflex vertices. Then the diameter of GT(Qn) is at most most 2(n + k - 4).

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.

#### Lemma 9:

Let T be any triangulation of Qn.  Then all the edges of R can be inserted in T using O(n) flips.

## Main Proof

We 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  By Christina Boucher cbouch35@cs.mcgill.ca