| Abstract Polygons Flip Finitely: Flaws and a Fix (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this as an open problem in 1935, several independent purported proofs have been published. However, we uncover a plethora of errors and gaps in these arguments, and remedy these problems with a new (correct) proof. 1 Pocket Flips Given a simple polygon in the plane, a pocket is a maximal connected region interior to the convex hull and exterior to the polygon. A (pocket) flip is the reflection of a pocket, or more precisely the subchain of the polygon bounding the pocket, across its line of support, the bounding edge of the convex hull. In 1935, Paul Erdős [3] introduced the problem of simultaneously flipping all pockets of a simple polygon, and repeating this process until the polygon becomes convex. He conjectured that this process terminates after a finite number of steps. In 1939, Béla Nagy [2] pointed out that flipping multiple pockets simultaneously may make the polygon nonsimple. Modifying the problem slightly, he argued that repeatedly flipping one pocket of the current polygon always convexifies the polygon after a finite number of flips. This result has come to be known as the Erdős-Nagy Theorem. Over the years, the theorem has been rediscovered many times, each discovery leading to a new proposed proof. Among the arguments published in English, some are long and technical, others use higher mathematics, some prove a weaker result, some leave gaps for the reader to fill, and still others are incorrect. In Section 2, we describe these arguments and point out their weaknesses, gaps, and errors. We view only one proof, by Kazarinoff and Bing [8, 1, 7], as completely correct, though terse. Then, in Section 3, we present our own proof which attempts to combine the most elegant portions of the existing arguments, along with a few new tricks, into a (correct) proof that we believe is both simple and thorough. 2 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||