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.

gollark: Fear it, although it isn't technically from that.
gollark: This application is LITERALLY a particle of weight W placed on a rough plane inclined at an angle of θ to the horizontal. The coefficient of friction between the particle and the plane is μ. A horizontal force X acting on the particle is just sufficient to prevent the particle from sliding down the plane; when a horizontal force kX acts on the particle, the particle is about to slide up the plane. Both horizontal forces act in the vertical plane containing the line of greatest slope.
gollark: Fiiiiine.
gollark: I agree. It's precisely [NUMBER OF AVAILABLE CPU THREADS] parallelized.
gollark: > While W is busy with a, other threads might come along and take b from its queue. That is called stealing b. Once a is done, W checks whether b was stolen by another thread and, if not, executes b itself. If W runs out of jobs in its own queue, it will look through the other threads' queues and try to steal work from them.

References
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.