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.
History
Paul Erdős conjectured the result in 1935 as a problem in the American Mathematical Monthly, and Szőkefalvi-Nagy published a proof in 1939. The problem has a curious history and had been repeatedly rediscovered, until Branko Grünbaum surveyed the results in 1995. As it turns out, the original proof had a delicate mistake, which has been since corrected.
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.
External links
This article is issued from Wikipedia - version of the 8/23/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.