Polygonal Ears and Triangulation Duals

In a 1975 paper, G. H. Meisters posed and proved the following

Two Ears Theorem

Except for triangles, every Jordan polygon has at least two non-overlapping ears.

Jordan polygon is a simple closed polygonal plane curve with a finite number of sides. Three consecutive vertices V1, V2, V3 of a Jordan polygon P = V1V2V3V4 ... VnVl are said to form an ear (regarded as the region enclosed by the triangle V1V2V3) at the vertex V2 if the (open) chord joining V1 and V3 lies entirely inside the polygon P. We say that two ears are non-overlapping if their interior regions are disjoint; otherwise they are overlapping.

Meisters proves his theorem by induction while considering several possible cases, with the greatest effort extended to deliver the ears that do not overlap. Over the years, many proofs of theorem have been found, with some disregarding this extra condition. An elegant proof below comes from J. O'Rourke's Computational Geometry in C, where (unlike in a more recent book of the same author) the theorem is stated as originally by Meisters but the "non-overlapping" condition is glossed over.

The dual of a triangulation of a polygon is a graph with a node associated with each triangle and an edge between two nodes if and only of their triangles share a diagonal.

Lemma

The dual of a triangulation is a tree, with each node of degree at most three.

Proof of Lemma

The degree of each of the nodes is at most three because a triangle in a triangulation may be adjacent to at most three other triangles.

If, on the contrary, the dual is not a tree, it contains a cycle. Position the nodes so that the edges cross the diagonals - the shared sides of two triangles. If that is hard, join the nodes to the midpoints of the diagonals that are to be crossed by the dual's edges. In any case, there is a closed polygon C' (that may be just C) that is entirely in the interior of the given polygon. If so, the interior of that polygon - that exists by the Jordan Curve Theorem - lies entirely in the interior of the given polygon. But this is impossible because C' crosses the diagonals and, therefore, has some of the original vertices in its interior. But vertices are on the boundary between the interior and exterior of the polygon, implying that within C' there are exterior points of the given polygon. This is certainly absurd.

Returning to the Two Ears Theorem, observe that every tree with more than two nodes has at least two leaves, but a leaf in a triangulation dual correspondents to a ear of the polygon.

The applet below is intended to illustrate this proof. The applet could be in one of two states. When the "Draw diagonals" box is checked, start dragging in a vicinity of one node and release the mouse in a vicinity of another. When the "Rearrange vertices" box is checked, choose the desired number of vertices and then drag them to obtain a polygon of a desired shape.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

(There is a more elementary proof of the theorem by induction and an application of the Pigeonhole Principle.)

References

  1. S. L. Devadoss, J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2012
  2. G. H. Meisters, Polygons Have Ears, Amer. Math. Monthly Vol. 82, No. 6 (Jun. - Jul., 1975), pp. 648-651
  3. J. O'Rourke, Computational Geometry in C, Cambridge University Press, 2001

|Activities| |Contact| |Front page| |Contents| |Geometry| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62038097

Search by google: