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 < P_{1}, P _{2},..., P_{n} > such that P_{1} = P, P_{n} = Q and polygon P_{i+1} is obtained from polygon P_{i} by applying a certain operation on P_{i}. 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.
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, P_{i+1} = f(P_{i}, (a_{i}, b_{i})) means that polygon P_{i+1} has been obtained from polygon P_{i} by flipping about the exposed pair of vertices (a_{i},b_{i}) of P_{i}.
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 p^{0}_{1},
p^{0} _{2},..., p^{0}_{s}
be the s vertices of the starting polygon P and let P_{i+1}
= f(P_{i}, (p^{i}_{k}, p^{i}_{l})),
with 1 <= k < l <= s. After flipping n
times, we obtain the polygon P _{n} with s vertices
p^{n} _{1}, p^{n}_{2},...,
p ^{n}_{s}. Since the perimeters of the P
_{i}'s is the same, there exists a circle that contain all polygons
in the sequence < P_{1}, P _{2}, ...,
P_{n} >. This implies that the sequence of vertices,
p^{0}_{k}, p^{1}_{k}, p^{2}_{k}
,..., or in other words, the sequence we obtain if we follow a particular
vertex p_{k }flip after flip, must stop somewhere inside
the circle containing all the P_{i }'s . We say that this
vertex p_{k} 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 P_{i}
and any point inside P_{i}, it follows that P_{n
}is the limit of the sequence of P _{i}'s. In other
words, the vertices of P_{n }are precisely the accumulation
points of the sequences of vertices p^{0}_{k}, p^{1}
_{k}, p^{2}_{k},..., for 1 <= k
<= s. Therefore, the sequence of P_{i}'s converges
to P_{n}.
Let C_{k} denote the convex hull of P_{k}. 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 P_{1}, C_{1}, P_{2}, C_{2}, P_{3}, C _{3},..., P_{n}, in which each polygon contains its predecessors. Since P_{n} is the limit of the sequence of P_{i}'s, it is also the limit of the sequence C_{i }'s. Therefore P_{n} is convex. Now, we show that the polygon P _{n} is actually obtained after a fintite number n of flips. Let p^{n}_{k} be a vertex of the final polygon P_{n}. We know that p^{n}_{k} is the limit of the sequence p^{1}_{k}, p^{2} _{k}, p^{3}_{k}, .... So there exists a positive number epsilon and a straight line L such that the circle c_{k}(epsilon) of radius epsilon centered at p^{n}_{k} can be lies completely on one side of line L while all other c_{l}(epsilon), k different from l, lie on the other side of L. If vertex p ^{i}_{k}, i <= n is the first of all p _{k}'s inside c_{k}(epsilon), then all the later p_{k}'s will also be inside c_{k}(epsilon), since the line L guarantees that this vertex will not belong to an arc that will be flipped. Thus, vertex p^{i}_{k} of P_{n} is immobilized after i(k) steps. The complete polygon P_{n} is immobilized after n = max{k=1..s}i(k) steps. |
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 P_{1}. If P_{1} is not convex, repeat the process, obtaining a new polygon P_{2}. Prove that after a finite number of such steps a polygon P_{n} 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 1^{st}
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.
[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.