Introduction

Suppose that we are given a simple polygon P, that is, a polygon which is not self-intersecting. We want to transform this polygon P into a convex polygon Q by a finite number of operations. In other words, we are interested in finding a finite sequence of polygons < P1, P 2,..., Pn > such that P1 = P, Pn = Q and polygon Pi+1 is obtained from polygon Pi by applying a certain operation on Pi. An algorithm for finding such a sequence of polygons is outlined in a paper by B. Grünbaum [1]. We shall introduce this algorithm formally and prove its correctness, but first we describe the intuitive idea behind the operation mentionned above.

Imagine a simple, non-convex polygon. Since it is non convex, there exists on this polygon at least one pair of vertices (a, b), such that the line segment ab is not an edge of the polygon but belongs to its convex hull. Such a line segments encloses what we will call a pocket (figure 1a)). The trick is basically to compute the convex hull of the polygon, to find a pocket and to flip it, i.e.to reflect it about the egde ab of the convex hull which encloses this pocket. By doing so, we obtain a new polygon with a convexified pocket (figure 1 b)). If, after having computed the convex hull of this new polygon, we cannot find another pocket, then we are done; our new polygon is convex. Otherwise, we choose a pocket and repeat the flipping operation.


Figure 1 : Pockets and an exposed pair.


Correctness of the Algorithm

Before proving the correctness of this method for convexifying any simple polygon, let us introduce some useful terminology and notation. A pair of points a and b of P such that P is entirely contained within one of the 2 closed halfspaces determined by the segment ab will be called an exposed pair. The flipping operation mentionned above will be denoted as a function f. For instance, Pi+1 = f(Pi, (ai, bi)) means that polygon Pi+1 has been obtained from polygon Pi by flipping about the exposed pair of vertices (ai,bi) of Pi.

Theorem 1:

         Any simple polygon P can be transformed into a convex polygon Q by a finite sequence of flips about lines determined at each stage by an exposed pair.


Proof :

         Let p01, p0 2,..., p0s be the s vertices of the starting polygon P and let Pi+1 = f(Pi, (pik, pil)), with 1 <= k < l <= s. After flipping n times, we obtain the polygon P n with s vertices pn 1, pn2,..., p ns. Since the perimeters of the P i's is the same, there exists a circle that contain all polygons in the sequence < P1, P 2, ..., Pn >. This implies that the sequence of vertices, p0k, p1k, p2k ,..., or in other words, the sequence we obtain if we follow a particular vertex pk flip after flip, must stop somewhere inside the circle containing all the Pi 's . We say that this vertex pk has a point of accumulation inside the circle. Since the flipping operation at step i either increases or leaves unchanged the distance between a vertex of Pi and any point inside Pi, it follows that Pn is the limit of the sequence of P i's. In other words, the vertices of Pn are precisely the accumulation points of the sequences of vertices p0k, p1 k, p2k,..., for 1 <= k <= s. Therefore, the sequence of Pi's converges to Pn.

Let Ck denote the convex hull of Pk. Every time we want to flip a pocket in a polygon, we first compute the convex hull to find a candidate pocket. So we have a sequence of polygons P1, C1, P2, C2, P3, C 3,..., Pn, in which each polygon contains its predecessors. Since Pn is the limit of the sequence of Pi's, it is also the limit of the sequence Ci 's. Therefore Pn is convex.

Now, we show that the polygon P n is actually obtained after a fintite number n of flips. Let pnk be a vertex of the final polygon Pn. We know that pnk is the limit of the sequence p1k, p2 k, p3k, .... So there exists a positive number epsilon and a straight line L such that the circle ck(epsilon) of radius epsilon centered at pnk can be lies completely on one side of line L while all other cl(epsilon), k different from l, lie on the other side of L. If vertex p ik, i <= n is the first of all p k's inside ck(epsilon), then all the later pk's will also be inside ck(epsilon), since the line L guarantees that this vertex will not belong to an arc that will be flipped. Thus, vertex pik of Pn is immobilized after i(k) steps. The complete polygon Pn is immobilized after n = max{k=1..s}i(k) steps.



Historical Notes

This problem was first proposed in 1935 by the Hungarian mathematician Paul Erdös [2]. His formulation of the problem was the following:

Given any simple polygon P which is not convex, draw the smallest convex polygon P' which contains P. This convex polygon P' will contain the area P and certain additional areas. Reflect each of these areas with respect to he corresponding added side, thus obtaining a new polygon P1. If P1 is not convex, repeat the process, obtaining a new polygon P2. Prove that after a finite number of such steps a polygon Pn will be obtained which will be convex.

We see that by 'step', Erdös actually meant simultaneously conducting the flips about all the exposed pairs of vertices of a polygon. Four years later, Sz.-Nagy [3] observed that such a 'step' could lead to a non-simple polygon, as illustrated in figure 2. He then reformulated the problem to require that the flips be carried out one at the time. He also gave a proof of the finiteness of the pocket-flipping method, which is essentially the proof outlined above. We also remark that Erdös mentionned the smallest convex polygon P' which contains P. Today we would describe this polygon P' as the convex hull of P. The same problem also appeared in papers from Reshetnyak [4] and Yusupov [5], both published in 1957. Apparently, neither was aware of Erdös' formulation of the problem and its solution by Sz.-Nagy. Their proofs differ in details from the one given above but follow the same ideas.


Figure 2 : A non-simple polygon.

In 1961, Bing and Kazarinoff published a joint paper[6] on this subject, in which they gave a new proof of Theorem 1 and claimed that the proof given by Sz.-Nagy was invalid. However, they did not justify this claim .They also wrote that the convexification of every simple polygon with n sides can be achieved with at most 2n flips, and claimed that Erdös proved this conjecture.

In 1973, R.R. Joss and R.W. Shannon, two graduate students at the University of Washington, found a simple counter-example to the Bing-Kazarinoff conjecture mentionned above. They also came up with a new method for convexifying a simple polygon. We shall now present these two results:


Joss and Shannon's 1st Theorem :

         For all positive integer m, there exist simple quadrangles that cannot be convexified by fewer than m flips.


Outline of the proof :

         Consider a quadrangle P with vertices a = (0,0), b = (2,0), c = (2 - cos 2A, sin 2A) and d = (cos A, sin A), where A is a small angle. Such a polygon is illustrated in figure 3 a). P has only one exposed pair, namely (a,c), and all derived polygons will also have only a single exposed pair. Since the images of vertices c and d always remain on unit circles centered at b and c as illustrated in figure 3 b), the number of flips required to convexify P increase without bound as we decrease A.



Figure 3 : Joss and Shannon's 1st theorem.

In order to illustrate Joss and Shannon's second result, we need to indroduce the concept of a flipturn: after having executed a flip about an exposed pair of verticex (a,b), we reflect the new arc about the line orthogonal to the midpoint of ab. Such a flipturn is illustrated in figure 4.


Figure 4 : A flipturn.

Joss and Shannon's 2nd Theorem :

         Any simple polygon with n sides can be convexified by a sequence of at most (n - 1)! flipturns.


Proof :

         If polygon Q is obtained from polygon P by a flipturn, the sides of P and Q are the same vectors and differ only by their cyclic order. There are at most (n - 1)! cyclic orders, and since each flipturn stricly increases the area of the polygon so that no permutation can be repeated, it follows that at most (n - 1)! flipturns are needed to obtain a convex polygon.

Note: The upper bound of (n - 1)! steps seems much too high. According to Grünbaum[1], Joss and Shannon conjectured that 1/4n 2 flipturns would be sufficient. However, they did not prove this conjecture, and by the time of Grünbaum's paper (1995), it was still an open problem.

Joss and Shannon intended to write an article with their results and they sent a copy of the preprint to Kazarinoff. This one replied that their work was "totally confusing" and did not deal at all with what he and Bing had in mind when they published their 1961 paper. This answer discouraged Joss and Shannon and they never published their work. Considering it shameful that their results were to be lost, Grünbaum presented them in his 1995 paper[1].



General Remarks

The algorithms described above assume that their input polygon is simple. Convexifying a non-simple polygon is still an open problem. Kazarinoff and Bing claimed in their paper that "simplicity of the polygon is not necessary". They did not however justify this claim. It seems that some other restrictions have to be put on non-simple polygons if we want to convexify them with one of these methods.

The flips and flipturns discussed above cannot be performed on arbitrary curves. Two recent papers ([7],[8]) deal with the operation of flipping smoth curves. An interesting result presented in [7] is that a suitable finite sequence of flips that has a convex curve as its limit can always be found , while in [8], it is shown that there exist curves which have a circle as the limit curve under a sequence of simultaneous flips, as in Erdös[2] method.



References

[1] B. Grünbaum, How to convexify a polygon. Geocombinatorics 5(1995), pp. 24-30.

[2] P. Erdös, Problem 3763. Amer. Math Monthly 42(1935), p.627.

[2] B. de Sz.-Nagy, Solution of problem 3763. Amer. Math, Monthly 49(1939), pp. 176-177.

[4] Yu.G. Reshetnyak, On a method of transforming a non-convex polygonal line into a convex one [in Russian]. Uspehi Mat. Mauk (N.S.) 12(1957), No 3(75), pp. 189-191.

[5] A.Ya Yusupov, A property of simply-connected non-convex polygons [in Russian]. Uchen. Zapiski Buharsk. Gos. Pedagog. Instituta, Tashkent, 1957, pp. 101-103.

[6] N.D. Kazarinoff and R.H. Bing, On the finiteness of the number of reflections that change a non-convex plane polygon into a convex one [In Russian]. Matematicheskoe Prosveshchenie 1961, No. 6, pp. 205-207.

[7] S.A. Robertson, Inflation of planes curves. Geometry and Topology of Submaniufolds, 111. World Scientific, 1991, pp. 264-275.

[8] S.A. Robertson and B. Wegner, Full and partial inflation of plane curves. Intuitive Geometry, Colloquia Math. Soc. János Bolyai vol. 63, North-Holland 1994, pp. 389-401.