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
Last updated May 17, 2017 by