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.
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.
|What if applet does not run?|
- S. L. Devadoss, J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2012
- G. H. Meisters, Polygons Have Ears, Amer. Math. Monthly Vol. 82, No. 6 (Jun. - Jul., 1975), pp. 648-651
- J. O'Rourke, Computational Geometry in C, Cambridge University Press, 2001
Copyright © 1996-2017 Alexander Bogomolny