Flipping Edged in Triangulations

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

# NUMBER OF FLIPPABLE EDGES

Given a triangulation T of a collection Pn = {v1,...,vn} 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.

#### Theorem 1:

Any triangulation of a collection of Pn of n points on the plane in general position contains at least ceiling[(n-4)/2] flippable edges.

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 (n-2)/4 edges are flippable

## General Position Assumption

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

 If we do not assume that no three points can be collinear then we must take polygons such as above in account.   Above: n-3 points in one of the sides of a triangle of a polygon with n points. We can see that if we have such a case than there exists a subset of edges which are not flippable because they are collinear.   In our example there are no flippable edges!

## Further notation

Given a triangulation T we can divide the set of edges of T into two subsets:

• F(T) which contains all flippable edges of T;
• NF(T) which contains all not flippable edges of T

Clearly all the edges of T contained in the boundary of the convex hull of Pn are not flippable.

We create an orientation of each edge e in NF(T) as follows:

• RULE 1:  If e is an edge of CH(Pn), orient it in the clockwise direction around CH(Pn) of Pn
 Rule 1: The following shows the orientation when the nonflippable edges are oriented around the convex hull.
• RULE 2:  If e=uv is not in CH(Pn), consider the quadrilateral C formed by the union of the two triangles of T containing e. Since C is not convex, it follows that one of the end vertices of e, say v, is a reflex vertex of C while u is a convex vertex of C. Orient e from u to v.  We observe that the angle of C at v is greater than 180 degrees.
 Rule 2: The following shows the orientation when the nonflippable edges are not convex hull edges.

Consider any vertex vi of T.  Let d-(vi) be the number of edges of vi in NF(T) oriented from vj to vi.  Note that d(vi) is the total number of edges of T incident with vi, whereas d-(vi) involves only edges of T in NF(T).

We use the following lemma to prove our main theorem...

#### Lemma 2:

Let vi be any vertex of T.  Then d-(vi) ≤ 3.  Moreover, if d(vi) > 3 in T, then d-(vi) ≤ 2.  If d-(vi) = 2, the edges oriented toward vi are consecutive edges around vi

#### Proof of  Lemma 2:

If vi is in CH(Pn) then d-(vi) = 1.  Next, suppose then that vi is in the interior of CH(Pn); then two cases arise:

Case 1: d(vi) = 3 in T.  In this case, all the edges of T incident with vi are nonflippable and are oriented toward vi. It follows that d-(vi) = 3

Case 2: d(vi) > 3 in T. It is obvious that no more than two edges of G can be oriented toward dvi and that if d-(vi) = 2, then the two edges oriented toward vi must be consecutive edges incident to vi

In the Below figured the oriented, nonflippable edges are the dashed lines whereas the flippable edges are solid.

 On the left the leftmost vertex has total degree 4 and 2 nonflippable edges.  Thus, the edges are consecutive. On the right vertex does not have valid degree. The total degree is 5 but the number of nonflippable edges is 3.  From lemma 2, this is not valid.

## Main Theorem

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

 Let Pn be a set of points in general position on the plane (see below) let T be a triangulation of Pn (see below)   In our triangulation we let S be the set of elements of Pn with degree 3 in T that are not in CH(Pn).  Step 3: Add an auxiliary point and join it to each of the points on the convex hull of our triangulation.  We add a point w exterior to CH(Pn) and join it with a set of disjoint edges to all the vertices in CH(Pn).  By this we obtain a triangulation of the plane with n+1 points which by Euler's theorem contains 3n-3 edges. Above we see that the point w added is the bottom most point.

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(Pn).  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-(vi) = 2 for all the elements of Pn of CH(Pn).

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 3|S| edges of T which are not flippable and what remains is a triangulation T' of Pn - S + {w}, which by Euler's formula contains 2(|Pn - S| + 1) - 4 = 2(n - |S|) - 2 triangles. Any element vi of Pn - S + {w} that is not in the convex hull of vertices of Pn - S + {w} that have d-(vi) = 2.

Step 7: Use lemma 2 on the resulting graph of step 6.

Using lemma 2 we can associate to every vertex vi of Q in the interior of CH(Pn) a triangle t(vi) of T' which is also a triangle in T, bounded by two oriented edges and the triangles t(vi) are all different. To each vertex vi of T' in CH(Pn) 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-(vi) < 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 vi not in S have d-(vi) = 2.  We have n - |S| triangles associated with vertices in Q and as T' has 2n - 2|S| - 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) - 3|S| - 2(n - |S|)   =   n - |S| - 3  ≥  (n - 4)/2

which is the number of flippable edges in T.

## Analogous Results for Polygons

We have analogous result of Theorem 1 for polygons.

#### Theorem 3:

Any triangulation of a polygon Qn with n vertices, k of them being reflex, contains at least n - 3 - 2k diagonals that can be flipped.

 Last Updated December 2, 2003  By Christina Boucher cboucher@geeky.net