Demaine - Polygons Flip.pdf - Topologia i Geometria - renvox

CCCG 2006, Kingston, Ontario, August 14–16, 2006

Polygons Flip Finitely: Flaws and a Fix

Erik D. Demaine

Blaise Gassend †

Joseph O’Rourke ‡

Godfried T. Toussaint §

Abstract

and y . Call a vertex of a simple polygon ﬂat if its interior

angle is . Let P=P 0 =hv 0 ,v 1 ,...,v n−1 i denote the

initial polygon and its vertices. Let P k =hv k 0 ,v k 1 ,...,v k n−1 i

denote the resulting “descendant” polygon after k arbitrary

pocket ﬂips; if P k is convex for some k , then we deﬁne P k =

P k+1 =P k+2 =··· . Let C k denote the convex hull of P k .

When we talk about convergence, it is always with respect to

k!1 . When the limit of P k exists, we denote it by P ,

its vertices by v i , etc.

Every simple planar polygon can undergo only a ﬁnite num-

ber of pocket ﬂips before becoming convex. Since Erdos

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.

1PocketFlips

2.1Nagy

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) ﬂip is the reﬂection 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 os [3] introduced the problem

of simultaneously ﬂipping all pockets of a simple polygon,

and repeating this process until the polygon becomes con-

vex. He conjectured that this process terminates after a ﬁnite

number of steps. In 1939, Bela Nagy [2] pointed out that ﬂip-

ping multiple pockets simultaneously may make the polygon

nonsimple. Modifying the problem slightly, he argued that

repeatedly ﬂipping one pocket of the current polygon always

convexiﬁes the polygon after a ﬁnite number of ﬂips.

This result has come to be known as the Erdos-Nagy The-

orem. 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 ﬁll, and

still others are incorrect. In Section 2, we describe these ar-

guments 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 sim-

ple and thorough.

The very ﬁrst claimed proof, published by Bela de Sz.-Nagy

in 1939 [2], is brilliant in overall design, but unfortunately

has a fatal ﬂaw that may have gone undetected until now. 1

Nagy’s argument consists of the following main steps:

1. The sequence P k converges.

2. The limit P is convex.

3. Nonﬂat vertices of P converge in ﬁnite time.

4. The sequence P k converges in ﬁnite time.

The ﬂaw is in Step 2, where Nagy uses the claim that

P 0 C 0 P 1 C 1 ... to show that P k and C k con-

verge to the same (necessarily convex) limit. As illustrated

in Figure 1, this claim is incorrect. When there are multiple

pockets to choose from, C k 6P k+1 .

P 0 P 1

C 0 C 1

Figure 1: Nagy’s error: P 0 C 0 6 P 1 C 1 .

Despite most later arguments being based on Nagy’s, this

ﬂaw seems unique to Nagy’s argument. Many later argu-

ments use the other steps of Nagy’s argument, to which we

now turn.

In Step 1, Nagy observes that the perimeter of P k is

constant, and concludes that each v k i has a point of ac-

cumulation. Then he observes that, for x inside P k and

mk , d(x,v m i )<d(x,v m+ i ) .

2ExistingArguments

We begin by introducing some notation used in this paper.

Let d(x,y) denote the Euclidean distance between points x

Therefore, for nm ,

edemaine@mit.edu. Supported by NSF and DOE.

† gassend@alum.mit.edu

‡ orourke@cs.smith.edu. Supported by NSF DUE-0123154.

§ godfried@cs.mcgill.ca. Supported by NSERC and FQNRT.

1 We should point out, though, that Gr unbaum [4] states that Bing

and Kazarinoff [1] remark that Nagy’s proof [2] is invalid. However,

Gr unbaum [4] goes on to say that there is no basis for this claim. We have

not yet seen the Russian paper [1] and thus cannot assess this point further.

18th Canadian Conference on Computational Geometry, 2006

2.3ReshetnyakandYusupov

v i

In 1957, two papers in Russian by Reshetnyak [9] and

Yusupov [13] claimed proofs of the theorem. According to

Gr unbaum [4], these arguments are similar to Nagy’s [2]. We

have not yet studied the differences in detail.

v i−1 v i−1

Figure 2: For a nonﬂat vertex v k i , once all the vertices are within

a small enough ball around their limit, there is a line which sepa-

rates the ball of v k i from all the other balls. Thus v k i subsequently

remains on the convex hull of P k and cannot be ﬂipped again.

2.4KazarinoandBing

In 1959, Kazarinoff and Bing [8] announced the problem and

a solution. Two years later, a proof appeared in a paper by

Bing and Kazarinoff [1] and also in Kazarinoff’s book [7].

They also conjectured that every simple polygon becomes

convex after at most 2n ﬂips. This conjecture has since been

shown to be false; see Section 2.5.

The proof described in Kazarinoff’s book [7] has no miss-

ing steps, and suffers only from being terse. Our proof distin-

guishes itself mainly by providing more detail. Their proof

proceeds as follows:

1. The sequence P k converges to a limit P .

2. Nonﬂat vertices of the convex hull of P converge in

ﬁnite time.

3. All vertices of P k converge in ﬁnite time. (Same idea

as Nagy.)

For Step 1, Kazarinoff and Bing use the “constant poly-

gon length” and the “distances from points in the polygon

increase” arguments. They show that, for x interior to C 0 ,

the sequence d(x,v k i ) is bounded and monotonic, and thus

it converges. Applying this argument for three noncollinear

points x 1 , x 2 , and x 3 shows that each v k i converges to the

unique intersection of three circles.

In Step 2, they argue that, because P k converges, its in-

terior angles must also converge. Thus, any vertex that con-

verges to a nonﬂat vertex of C has an interior angle less than

after a ﬁnite number of steps. Because a vertex moves only

when it is ﬂipped, and a ﬂip changes an interior angle into

the angle 2− , the vertex can no longer move.

d(v m i ,v n i )<d(v m i ,v n+ i ) , which prevents the existence of

multiple points of accumulation, thus proving convergence.

To prove Step 3, Nagy uses an argument illustrated in Fig-

ure 2 to show that nonﬂat vertices of the limit polygon con-

verge in ﬁnite time. This argument is easy to draw, but re-

quires care to justify in detail, while Nagy’s presentation is

somewhat terse.

Finally, in Step 4, once all the nonﬂat vertices have con-

verged, no more ﬂips are possible, because they would cause

the convex hull to increase beyond its limit.

2.2Gr¨unbaum

Branko Grunbaum [4] described some of the intricate his-

tory of this problem following the appearance of Nagy’s pa-

per [2], uncovering several rediscoveries of the theorem. He

also provided his own argument, similar to Nagy’s but more

terse. One main difference is that, at each step, he ﬂips the

pocket that has maximum area (if there is more than one

pocket to choose from). Therefore Grunbaum [4] actually

proves a weaker theorem: there exists a (well-chosen) se-

quence of ﬂips that convexiﬁes after ﬁnitely many ﬂips. An

extended version of [4] was published in 2001 by Grunbaum

and Zaks [5].

Gr unbaum’s argument has a similar structure to Nagy’s:

1. A subsequence of the sequence P k converges to a con-

vex limit.

2. The whole sequence converges.

3. Nonﬂat vertices of the limit polygon converge in ﬁnite

time. (Same proof as Nagy.)

4. The sequence converges in ﬁnite time. (Same as Nagy.)

2.5JossandShannon

In 1973, two students of Gr unbaum at the University of

Washington, R. R. Joss and R. W. Shannon, worked on this

problem but did not publish their results. Gr unbaum [4]

gives an account of the unfortunate circumstances surround-

ing this event. They found a counterexample to the conjec-

ture of Bing and Kazarinoff (but unaware of the conjecture).

Speciﬁcally, they showed that, given any positive integer k ,

there exist simple polygons of constant size (indeed, quadri-

laterals sufﬁce) that cannot be convexiﬁed with fewer than k

ﬂips. See [4, 11].

For Step 1, Grunbaum invokes Nagy’s “constant polygon

length” argument to show that a subsequence converges. He

then claims that “due to the selection of pockets that maxi-

mize the area, the limit polygon P is convex,” without fur-

ther explanation. We view this unjustiﬁed claim as a gap in

the proof, because the convexity of P has been a stumbling

block in most claimed proofs of the theorem.

In Step 2, Gr unbaum invokes Nagy’s “distances from

points in the polygon increase” observation, without further

justiﬁcation. As in Nagy’s proof, this argument seems insuf-

ﬁcient by itself, requiring more detail.

2.6Wegner

In 1981, Kaluza [6], apparently unaware of the previous

work, posed the problem again and asked whether the num-

ber of ﬂips could be bounded as a function of the number

CCCG 2006, Kingston, Ontario, August 14–16, 2006

of polygon vertices. In 1993, Bernd Wegner [12] took up

Kaluza’s challenge and solved both problems again. His

proof of convexiﬁcation in a ﬁnite number of ﬂips is quite

different from the others, but his example of unboundedness

is the same as that of Joss and Shannon.

Wegner’s proof is certainly the most intricate of the proofs

we have seen. His proof is very technical, for example, us-

ing convergence results from the theory of convex bodies,

and difﬁcult to summarize. To his credit, Wegner carefully

details his reasoning, unlike many other authors.

Wegner’s approach contains a number of new ideas. He

notices that the undirected angles between consecutive poly-

gon edges are monotonically nondecreasing, as they only

change when a vertex is on the edge of the lid being ﬂipped.

The use of undirected angles makes this property stand out,

but prevents the use of angles to show convergence in ﬁnite

time as in Kazarinoff’s proof [7].

Instead, Wegner introduces the area A k of P k and tries

to show that, after a ﬁnite number of ﬂips, performing an

additional ﬂip would cause A k to exceed the area A of its

limit. He lower-bounds the increase in area during a ﬂip that

moves vertex v k i by considering the area a of the triangle

v k i−1 v k i v k i+1 . Wegner argues that, during such a ﬂip, A k will

increase by at least 2a , and uses this fact to force A k beyond

its limit. However, as illustrated in Figure 3, the increase in

area by 2a occurs only for reﬂex vertices v k i . Fortunately,

this ﬂaw is easy to ﬁx, because a convex vertex becomes

reﬂex after one ﬂip, so the next time it moves, Wegner’s ar-

gument indeed applies.

ported.) This led the ﬁrst and third authors of this paper to

point out the problem, and propose the three-point solution.

This correction appeared in the journal version of Toussaint’s

argument [11].

Unfortunately, both arguments [10, 11] make an invalid

deduction for establishing the convexity of the limit poly-

gon P : “we note that the limit polygon must be convex, for

otherwise, being a simple polygon, another ﬂip would alter

its shape contradicting that it is the limit polygon.” For some

intuition on why this deduction is invalid, imagine that there

are two portions of the polygon that each inﬂate inﬁnitely

often (hypothetically, of course). If we spend all of our time

ﬂipping just one of those portions, the other portion never

gets ﬂipped, so the limit is nonconvex.

3ProofoftheErd˝os-NagyTheorem

We now offer a short, elementary, and self-contained proof

of the Erd os-Nagy Theorem. After writing our proof, we

discovered that it uses essentially the same arguments as

Kazarinoff and Bing [8]. The main difference is that we en-

deavored to detail all important steps. As we shall see in

Section 3.1, this led to some small changes from [8] which

we feel enhance the clarity of the proof.

Theorem 1 A simple polygon P can undergo only a ﬁnite

number of pocket ﬂips before being convexiﬁed.

Proof. Reasoning by contradiction, suppose that there were

an inﬁnite sequence of polygons P k =hv k 0 ,...,v k n−1 i , in-

dexed by k , each P k derived from the previous P k−1 by

exactly one pocket ﬂip (i.e., the sequence P k never becomes

constant), starting from P 0 =P . Let x be any point in-

side P . By deﬁnition of ﬂipping, we have P 0 P 1 ···

P k , so x is inside all descendants of P .

We ﬁrst offer an outline of the proof:

1. The distance from each vertex v k i to a ﬁxed point x2P

is a monotonically nondecreasing function of k .

2. The sequence P k approaches a limit polygon P .

3. The angle k i at vertex v k i converges.

4. Any vertex v k i that moves inﬁnitely many times con-

verges to a ﬂat vertex v i .

5. The inﬁnite sequence P k cannot exist.

Step 1. First we prove that the distance from x to any

particular vertex v i is monotonically nondecreasing with k .

Let d(x,v k i ) be this distance at step k . If the (k+1) st ﬂip

does not move v i , then the distance remains the same. If v i

is ﬂipped, then it ﬂips over the pocket’s line of support, L ,

which is the perpendicular bisector of v k i v k+ i ; see Figure 4.

Because L supports the hull of P k and x is inside P k , x is

on the same side of L as v k i . Thus d(x,v k+ i )>d(x,v k i ) .

This establishes that the distance from x to each vertex is a

monotonically nondecreasing function of k .

Step 2. Next we argue that the sequence P k approaches a

limit polygon P . The perimeter of P k is independent of k ,

Figure 3: Flipping a reﬂex vertex increases the polygon area by

twice the area a of the incident triangle (left), but this property is

not true of a convex vertex (right).

2.7Toussaint

Motivated by the desire to present a simple, clear, elemen-

tary, and pedagogical proof of such a beautiful theorem, Tou-

ssaint [10] presented a more detailed and readable argument

at CCCG 1999. He combined Kazarinoff and Bing’s ap-

proach to proving the convergence of P k with Nagy’s ap-

proach of proving that convergence occurs in ﬁnite time.

The original argument that appeared in [10] uses one in-

stead of three noncollinear points x 1 , x 2 , and x 3 to conclude

that the vertices v k i converge. However, without further jus-

tiﬁcation, it is plausible that v k i circles around x and thus has

multiple accumulation points. Because Toussaint’s argument

is explicit in the details, this issue is clearly an error. (This is

unlike Gr unbaum’s argument where the reader is left guess-

ing whether Gr unbaum was in error or left some trick unre-

18th Canadian Conference on Computational Geometry, 2006

v k+1

polygons and so in P C . So we have reached Fact B:

P ¯ k+1 C C ¯ k . Fact B contradicts Fact A, so there

cannot be an inﬁnite sequence P k .

v k i

3.1Discussion

To close, we outline some of the main differences between

our proof and other arguments, particularly Kazarinoff and

Bing’s proof [8], which make exposition easier:

1. Whereas previous authors prove that P k becomes con-

stant after a ﬁnite number of steps, we prefer to reason

by contradiction, proving that an inﬁnite number of ﬂips

is impossible. This simpliﬁes our reasoning. For exam-

ple, it allows us to conclude that P k+1 always contains

points not in C k . Otherwise, this relation would only

hold until the polygon has convexiﬁed.

2. We use directed angles instead of interior angles. This

approach allows us to talk about limit angles without

worrying about whether the limit polygon is simple.

3. We show that nonﬂat vertices of P converge in ﬁnite

time. Kazarinoff and Bing [8] use vertices of C in-

stead, and consider that all vertices of C are nonﬂat.

Unfortunately, this view means that there can be fewer

vertices in C than in P k , so we lose the correspon-

dence between vertices of C and vertices of P k .

Figure 4: The distance from x to v i increases by a ﬂip.

for it is just the sum of the ﬁxed edge lengths. The distance

from x to v i is bounded above by half the perimeter (because

the polygon has to wrap around both x and v i ). Thus each

distance sequence d(x,v k i ) has a limit. If we look at the dis-

tance sequences to v i from three noncollinear points x 1 , x 2 ,

and x 3 inside P , their limits determine three circles (centered

at x 1 , x 2 , and x 3 ) whose unique intersection point yields a

limit position v i . Then P =hv 0 ,...,v n−1 i .

Step 3. Let k i 2[0,2) be the directed angle

\v k i−1 v k i v k i+1 . We observe that k i 2[ i ,2− i ] , where

i =min{ k i ,2− k i } . Indeed this relation holds for 0 i ,

and for k i to get closer to 0 or 2 , d(v k i−1 ,v k i+1 ) would have

to decrease, which is impossible by the distance argument

detailed in Step 1. Because k i stays away from 0 and 2 ,

and the edge lengths of P k are ﬁxed, and therefore cannot

approach zero, k i is a continuous function of the coordi-

nates of the three vertices in P k that deﬁne the angle. These

vertices converge, so k i must also converge, and its limit is

i =\v i−1 v i v i+1 .

Step 4. We now distinguish between ﬂat and nonﬂat ver-

tices of P . A ﬂat vertex v i is one for which i = . A

nonﬂat vertex has i 6= ; it could be convex or reﬂex.

Consider a vertex for which v k i moves an inﬁnite number

of times. We show that this vertex converges to a ﬂat vertex

v i of P . Indeed, when v k i moves as a result of a pocket ﬂip,

k+ i =2− k i , as befalls any directed angle which is re-

ﬂected. Consequently, there are inﬁnitely many k for which

k i , and inﬁnitely many for which k i . Thus the

limit i can only be .

Step 5. All that remains is to force a contradiction by

showing that, once the nonﬂat vertices of P have been

reached, no further ﬂips are possible. Here we use the convex

hull C k of P k , and the hull C of P . Of course, P k C k

and P C . We will obtain a contradiction to Fact A: for

any k , P k+1 6C k . The reason this fact holds is that, at ev-

ery ﬂip, the mirror image of the pocket area previously inside

C k is outside C k . (See, for example, Figure 1: P 1 6C 0 .)

Let ¯ k be a value of k for which only ﬂat vertices of P

have yet to converge. P ¯ k includes all nonﬂat vertices in their

ﬁnal positions. Of course, P also includes all nonﬂat ver-

tices in their ﬁnal positions. Now, because the ﬂat vertices

of P cannot alter its hull beyond what the nonﬂat vertices

already contribute, we know that C C ¯ k . ( C ¯ k is conceiv-

ably a proper superset because of the vertices of P k that are

destined to be, but are not yet, ﬂat vertices in P .)

Now consider P ¯ k+1 .

References

[1] R. H. Bing and N. D. Kazarinoff. On the ﬁniteness of the

number of reﬂections that change a nonconvex plane polygon

into a convex one. Matematicheskoe Prosveshchenie , 6:205–

207, 1961. In Russian.

[2] B. de Sz.-Nagy.

Solution of problem 3763.

Amer. Math.

Monthly , 46:176–177, 1939.

[3] P. Erdos. Problem 3763. Amer. Math. Monthly , 42:627, 1935.

[4] B. Gr unbaum. How to convexify a polygon. Geombinatorics ,

5:24–30, 1995.

[5] B. Gr unbaum and J. Zaks. Convexiﬁcation of polygons by

ﬂips and by ﬂipturns. Discrete Math. , 241:333–342, 2001.

[6] T. Kaluza.

Problem 2: Konvexieren von Polygonen.

Math.

Semesterber. , 28:153–154, 1981.

[7] N. D. Kazarinoff. Analytic Inequalities . Holt, Rinehart and

Winston, 1961.

[8] N. D. Kazarinoff and R. H. Bing. A ﬁnite number of re-

ﬂections render a nonconvex plane polygon convex. Notices

Amer. Math. Soc. , 6:834, 1959.

[9] Y. G. Reshetnyak. On a method of transforming a noncon-

vex polygonal line into a convex one.

Uspehi Mat. Nauk. ,

12(3):189–191, 1957. In Russian.

[10] G. T. Toussaint. The Erdos-Nagy theorem and its ramiﬁca-

tions. In Proc. 11th Canad. Conf. Comput. Geom. , pp. 9–12,

1999. Vancouver, Canada.

[11] G. T. Toussaint. The Erdos-Nagy theorem and its ramiﬁca-

tions. Comput. Geom. Theory Appl. , 31(3):219–236, 2005.

[12] B. Wegner. Partial inﬂation of closed polygons in the plane.

Contributions to Algebra and Geometry , 34(1):77–85, 1993.

[13] A. Y. Yusupov. A property of simply-connected nonconvex

polygons. Uchen. Zapiski Buharsk. Gos. Pedagog. , pp. 101–

103, 1957. In Russian.

It is contained in all subsequent

Demaine - Polygons Flip.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: