Paper by Erik D. Demaine

Erik D. Demaine, Blaise Gassend, Joseph O'Rourke, and Godfried T. Toussaint, “All Polygons Flip Finitely… Right?”, in Surveys on Discrete and Computational Geometry: Twenty Years Later, edited by J. Goodman, J. Pach, and R. Pollack, Contemporary Mathematics, volume 453, 2008, pages 231–255, American Mathematical Society. Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, June 18–22, 2006, Snowbird, Utah.

Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this finiteness as an open problem in 1935, several independent purported proofs have been published. However, we uncover a plethora of errors, gaps, and omissions in these arguments, leaving only two proofs without flaws and no proof that is fully detailed. Fortunately, the result remains true, and we provide a new, simple (and correct) proof. In addition, our proof handles nonsimple polygons with no vertices of turn angle 180°, establishing a new result and opening several new directions.

Copyright held by the authors.

The paper is 19 pages.

The paper is available in PostScript (4273k), gzipped PostScript (2161k), and PDF (422k).
See information on file formats.
[Google Scholar search]

Related papers:
Flips_CCCG2006 (Polygons Flip Finitely: Flaws and a Fix)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.