In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equivalent to the existence of polygon triangulations. It is frequently attributed to Gary H. Meisters, but was proved earlier by Max Dehn.
Statement of the theorem
editA simple polygon is a simple closed curve in the Euclidean plane consisting of finitely many line segments in a cyclic sequence, with each two consecutive line segments meeting at a common endpoint, and no other intersections. By the Jordan curve theorem, it separates the plane into two regions, one of which (the interior of the polygon) is bounded. An ear of a polygon is defined as a triangle formed by three consecutive vertices of the polygon, such that its edge lies entirely in the interior of the polygon. The two ears theorem states that every simple polygon that is not itself a triangle has at least two ears.[1]
Relation to triangulations
editAn ear and its two neighbors form a triangle within the polygon that is not crossed by any other part of the polygon. Removing a triangle of this type produces a polygon with fewer sides, and repeatedly removing ears allows any simple polygon to be triangulated. Conversely, if a polygon is triangulated, the weak dual of the triangulation (a graph with one vertex per triangle and one edge per pair of adjacent triangles) will be a tree and each leaf of the tree will form an ear. Since every tree with more than one vertex has at least two leaves, every triangulated polygon with more than one triangle has at least two ears. Thus, the two ears theorem is equivalent to the fact that every simple polygon has a triangulation.[2]
Triangulation algorithms based on this principle have been called ear-clipping algorithms. Although a naive implementation is slow, ear-clipping can be sped up by the observation that a triple of consecutive vertices of a polygon forms an ear if and only if the central vertex of the triple is convex and the triple forms a triangle that does not contain any reflex vertices. By maintaining a queue of triples with this property, and repeatedly removing an ear from the queue and updating the adjacent triples, it is possible to perform ear-clipping in time , where is the number of input vertices and is the number of reflex vertices.[3]
If a simple polygon is triangulated, then a triple of consecutive vertices forms an ear if is a convex vertex and none of its other neighbors in the triangulation lie in triangle . By testing all neighbors of all vertices, it is possible to find all the ears of a triangulated simple polygon in linear time.[4] Alternatively, it is also possible to find a single ear of a simple polygon in linear time, without triangulating the polygon.[5]
Related types of vertex
editAn ear is called exposed when its central vertex belongs to the convex hull of the polygon. However, it is possible for a polygon to have no exposed ears.[6]
Ears are a special case of a principal vertex, a vertex such that the line segment connecting the vertex's neighbors does not cross the polygon or touch any other vertex of it. A principal vertex for which this line segment lies outside the polygon is called a mouth. Analogously to the two ears theorem, every non-convex simple polygon has at least one mouth. Polygons with the minimum number of principal vertices of both types, two ears and a mouth, are called anthropomorphic polygons.[7] Repeatedly finding and removing a mouth from a non-convex polygon will eventually turn it into the convex hull of the initial polygon. This principle can be applied to the surrounding polygons of a set of points; these are polygons that use some of the points as vertices, and contain the rest of them. Removing a mouth from a surrounding polygon produces another surrounding polygon, and the family of all surrounding polygons can be found by reversing this mouth-removal process, starting from the convex hull.[8]
History and proof
editThe two ears theorem is often attributed to a 1975 paper by Gary H. Meisters, from which the "ear" terminology originated.[1] However, the theorem was proved earlier by Max Dehn (circa 1899) as part of a proof of the Jordan curve theorem. To prove the theorem, Dehn observes that every polygon has at least three convex vertices. If one of these vertices, v, is not an ear, then it can be connected by a diagonal to another vertex x inside the triangle uvw formed by v and its two neighbors; x can be chosen to be the vertex within this triangle that is farthest from line uw. This diagonal decomposes the polygon into two smaller polygons, and repeated decomposition by ears and diagonals eventually produces a triangulation of the whole polygon, from which an ear can be found as a leaf of the dual tree.[9]
References
edit- ^ a b Meisters, G. H. (1975), "Polygons have ears", The American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703, MR 0367792.
- ^ O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, Oxford University Press, ISBN 0-19-503965-3, MR 0921437.
- ^ Held, M. (2001), "FIST: fast industrial-strength triangulation of polygons", Algorithmica, 30 (4): 563–596, doi:10.1007/s00453-001-0028-4, MR 1829495, S2CID 1317227
- ^ Highnam, P. T. (1982), "The ears of a polygon", Information Processing Letters, 15 (5): 196–198, doi:10.1016/0020-0190(82)90116-8, MR 0684250
- ^ ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried (September 1993), "Slicing an ear using prune-and-search", Pattern Recognition Letters, 14 (9): 719–722, Bibcode:1993PaReL..14..719E, doi:10.1016/0167-8655(93)90141-y
- ^ Meisters, G. H. (1980), "Principal vertices, exposed points, and ears", The American Mathematical Monthly, 87 (4): 284–285, doi:10.2307/2321563, JSTOR 2321563, MR 0567710.
- ^ Toussaint, Godfried (1991), "Anthropomorphic polygons", The American Mathematical Monthly, 98 (1): 31–35, doi:10.2307/2324033, JSTOR 2324033, MR 1083611.
- ^ Yamanaka, Katsuhisa; Avis, David; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Algorithmic enumeration of surrounding polygons", Discrete Applied Mathematics, 303: 305–313, doi:10.1016/j.dam.2020.03.034, MR 4310502
- ^ Guggenheimer, H. (1977), "The Jordan curve theorem and an unpublished manuscript by Max Dehn" (PDF), Archive for History of Exact Sciences, 17 (2): 193–200, doi:10.1007/BF02464980, JSTOR 41133486, MR 0532231, S2CID 121684753.