Flipping Edged in Triangulations

BOUND ON THE DIAMETER G_T(P_n)

Theorem for G_T(P_n) 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 P_n_, G_T(P_n).

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

Theorem 5:

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

Helpful Lemmas and Theorems

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 Q_i,j be the subpolygon of Q obtained by joining all the triangles of T intersected by v_iv_j. Let T' be the triangulation induced by T in Q_i,j. Let t be the number of edges that v_iv_jis 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_iv_jis intersected by t-1 edges. Let u₁,...,u_m denote the vertices of Q_i,j between v_iand v_jin the clockwise direction. Let u_t be a convex vertex of Q_i,j (there is at least one convex vertex otherwise v_iand v_jwould not be visible in Q). If u_t is in T' then it is adjacent to exactly one vertex in the set {v₁₊₁,...,v_j-1} and the edge connecting them in T' can be flipped. After flipping the stated edge, the number of edge that intersect v_iv_jsay v_s-1v_s is reduced by 1. Then the edge u_tv_s intersecting v_s-1v_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_j-1.

Proof of Lemma 6

Since u_t is convex, we can flip u_tv_s+1 and then flip u_tv_s. The number of edges intersecting v_iv_j has gone down by one. Our result now follows.

Finally suppose that Q has k reflex vertices labeled v_i1,...,v_iksuch that i1 <...< ik. For each j = 1,...,k let R_j be the shorted polygonal chain containing Q joining v_jto v_j+1. Let R = R₁ U ... U R_k.

Polygon R is in bold.

Lemma 7:

Let T any triangulation of P_n. 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 C₁ and C₂respectively. An edge of T can cross C₂ at most twice. If an edge of T crosses C₂ twice then the endpoints are in C₁. Let r denote the the number of edges that cross C₂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₂twice and w be a vertex such that uvw is a triangle of T. Suppose w is not in C₁ then it can be flipped and a new edge is obtained which crosses C₂ at most once.

If uv does not cross an edge of C₂ twice then either uw or vw crosses C₂twice and the process is continued until a flippable edge is found.

Now we assume that no edge of T crosses C₂ twice. Then we let for every edge e of C₂ 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₂. Thus, we now can conclude that C₂ 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₁,..., v_s,v_s+1,...,v_n such that v₁,...,v_sare 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

Lemma 8:

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

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_jbe the shortest polygonal chain contained in Q_n joining v_ij to v_i(j+1), addition mod k. Then let R = R₁U...U R_k.

Then we have the following lemma.

Lemma 9:

Let T be any triangulation of Q_n. 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 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₁ and T₁'.

We denote the first and second convex layers as: C₁ = {v₁,..., v_q} and C₂ = {u₁,...,u_p}. Without loss of generality, let u₁v₁ be a vertex which does not cross C₂.

Re-triangulate the polygon between C₁and C₂ as follows. u1v1 is a proper diagonal and so it can be inserted both in T₁ and T₁' with O(n) flips using lemma 8. This creates Q = v₁...v_qv₁u₁u_p....u₂u₁, a spiral polygon. Using Lemma 7 the triangulations induced by T₁ and T₁' in Q can be transformed into each other with O(n) flips. The process is repeated inside C₂ 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

BOUND ON THE DIAMETER GT(Pn)

Theorem for GT(Pn) for point sets