Feature Column from the AMS

Diagonals: Part I

3. Triangulations and ears

If you try some experiments you will discover that every plane simple polygon has an interior diagonal. However, it may not be so easy to prove that this is true. In fact, some early attempts to prove this result, on the way to showing that every plane simple polygon could be subdivided into triangles, were not correct.

If one can show that every simple polygon has a diagonal, then one can use this result repeatedly to subdivide a polygon into triangles. For example, the red diagonals in the figure below show how to turn all of the subdivided regions in the interior of the polygon in Figure 1 (in the previous section) into triangles.

While this polygon has the property that diagonals can be added in many ways to subdivide the polygon into triangles, the polygon in the diagram below has only one way to add diagonals to subdivide it into triangles.

A polygon which can be triangulated in only one way

Also, note that the diagonal edges can form circuits, or for some polygons, the diagonal edges can form a tree (e.g. a connected graph which has no circuits).

A triangulated polygon whose internal diagonals form a tree

How can one prove that there always exists a collection of diagonals which will triangulate a polygon? One very appealing way to approach this problem uses a theorem of Gary Meisters, known as the Ear Theorem:

Theorem: (Meisters)

Every simple polygon has at least two ears.

What is an ear? If one takes two consecutive edges uv and vw of a polygon, and the line segment that joins vertices u and w is an internal diagonal, then vertex v is called an ear of the polygon.

In the polygon above, there are exactly three ears: v, x, and z. Notice that the interior angles at y and w are more than 180 degrees, while the interior angle at u is less than 180 degrees. Vertices such as w and y aresometimes referred to as reflex vertices while vertices such as u, v, x, and z are referred to as convex vertices.

The polygon below has exactly two ears:

Can you see how to modify this example to create an infinite family of polygons which have exactly two ears? It turns out that although one can use the Ear Theorem to prove that every simple polygon can be triangulated, one can also prove this fact independently of the Ear Theorem and use it to prove the Ear Theorem.

The theorem that every simple polygon can be triangulated is used as one of the steps in the proof of the delightful result known as the Bolyai-Gerwien-Wallace Theorem. This result says that if two simple polygons P and Q have the same area, then one can cut up one of the polygons, say P, into a finite number of pieces and reassemble the pieces to form Q.