Erdős–Nagy theorem
The Erdős–Nagy theorem is a result in discrete geometry stating that a non-convex simple polygon can be made into a convex polygon by a finite sequence of flips. The flips are defined by taking a convex hull of a polygon and reflecting a pocket with respect to the boundary edge. The theorem is named after mathematicians Paul Erdős and Béla Szőkefalvi-Nagy.
Statement
A pocket of a non-convex simple polygon is a simple polygon bounded by a consecutive sequence of edges of the polygon together with a single edge of its convex hull that is not an edge of the polygon itself. Every convex hull edge that is not a polygon edge defines a pocket in this way. A flip of a pocket is obtained by reflecting the polygon edges that bound the pocket, across a reflection line containing the convex hull edge. Because the reflected pocket lies entirely within the reflected image of the convex hull, on the other side of this line, this operation cannot introduce any crossings, so the result of a flip is another simple polygon, with larger area.
In some cases, a single flip will cause a non-convex simple polygon to become convex. Once this happens, no more flips are possible. The Erdős–Nagy theorem states that it is always possible to find a sequence of flips that produces a convex polygon in this way. More strongly, for every simple polygon, every sequence of flips will eventually produce a convex polygon, in a finite number of steps.
There exist quadrilaterals that require an arbitrarily large (but finite) number of flips to be made convex. Therefore, it is not possible to bound the number of steps as a function of the number of sides of the polygon.
History
Paul Erdős conjectured the result in 1935 as a problem in the American Mathematical Monthly. In the version posed by Erdős, all pockets are to be flipped simultaneously; however, this may cause the polygon to become non-simple, as two pockets may flip on top of each other. In 1939, Szőkefalvi-Nagy pointed out this problem with Erdős's formulation, reformulated the problem in its now-standard form, and published a proof. Szőkefalvi-Nagy's proof had an incorrect case, which was pointed out in a 1995 survey of the problem by Branko Grünbaum; however, the proofs by Grünbaum and Godfried Toussaint are similarly incomplete. Additional proofs (some but not all correct) were provided in 1957 by two independent Russian mathematicians, Reshetnyak and Yusupov, in 1959, by Bing and Kazarinoff, and in 1993 by Wegner. Demaine, Gassend, O'Rourke, and Toussaint survey this history and provide a corrected proof.
Variations
An alternative method of making non-convex polygons convex that has also been studied is to perform flipturns, 180-degree rotations of a pocket around the midpoint of its convex hull edge.
References
- Branko Grünbaum, How to convexify a polygon, Geombinatorics, 5 (1995), 24–30.
- Godfried Toussaint, The Erdős–Nagy Theorem and its Ramifications, Proc. 11th Canadian Conference on Computational Geometry (1999), 219–236.
- Branko Grünbaum and Joseph Zaks, Convexification of polygons by flips and by flipturns, Discrete Math. 241 (2001), 333–342.
- E.D. Demaine, B. Gassend, J. O'Rourke, G.T. Toussaint, All polygons flip finitely right? Surveys on discrete and computational geometry, 231–255, in Contemp. Math., 453, Amer. Math. Soc., Providence, RI, 2008.