Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 42 (2001), No. 2, 307-311.

Simple Polygons with an Infinite Sequence of Deflations

Thomas Fevens^{1} Antonio Hernandez^{2} Antonio Mesa^{2} Patrick Morin^{3} Michael Soss^{1} Godfried Toussaint^{1}

School of Computer Science, McGill University 3480 University Street, Montreal, Quebec Canada H3A 2A7 e-mail: godfried@cs.mcgill.ca

Abstract. Given a simple polygon in the plane, a deflation is defined as the inverse of a flip in the Erdős-Nagy sense. In 1993 Bernd Wegner conjectured that every simple polygon admits only a finite number of deflations. In this note we describe a counterexample to this conjecture by exhibiting a family of polygons on which deflations go on forever.

1. Introduction

In 1993 Bernd Wegner [11] proposed a very interesting variant of Erdős-Nagy flips which can be considered the inverse problem. Recall that an Erdős-Nagy flip reflects a pocket of the convex hull of a simple polygon across its line of support. In 1935 Paul Erdős [4] conjectured that every simple polygon can be convexified in a finite number of flips. This conjecture was proved in 1939 by Bela Nagy [2]. Since then this problem has had a colorful history of many independent re-discoveries in a variety of fields ranging from mathematics to polymer physics and robotics resulting in several different proofs [10]. More recently Grünbaum [5] in 1995 used a variant of Nagy’s proof in which the flip selected at each iteration was chosen so as to maximize the increase in area of the resulting polygon. On the other hand, in 1993 Wegner [11] proved the theorem for all sequences of flips. The last rediscovery of this result is due to Biedl et al. [1].

1MacGill University ^{2} University of Havana ^{3} Carleton University 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2001 Heldermann Verlag

Figure 1. (a) A possible deflation operation on a simple polygon P (b) The resulting polygon P′ after the deflation

Wegner [11] defined the inverse problem as follows. Given a simple polygon P in the plane, if there exists a pair of non-adjacent vertices A_{i} and A_{j} such that the line through A_{i} and A_{j} is not a line of support of P, the line intersects the boundary of the polygon only at A_{i} and A_{j}, and the polygonal chain A_{i}, A_{i+1}, …, A_{j} can be reflected about this line to lie inside the polygon then this reflection operation is called a deflation. For example, consider the polygon P in Figure 1 (a). The line L through vertices A and B determines one possible deflation. The resulting polygon P′ after the deflation is illustrated in Figure 1 (b). If this cannot be done the polygon is called deflated. Wegner conjectured that for every simple polygon every sequence of deflations is finite.

2. The counterexample

In this note we exhibit a counterexample to the conjecture by showing that there exist simple polygons on which one can perform deflations an infinite number of times. Consider a quadrilateral with vertices A, B, C, D in clockwise order with the conditions that (1) the lengths of AB and CD sum to the remaining lengths BC and AD, and (2) that no two adjacent edges have the same length. Note that condition (1) alone is not sufficient to cause an infinite number of deflations. For example, the square and kite in Figure 2 both satisfy condition (1) and yet the square is already deflated and the kite in Figure 2 (b) is deflated after at most one deflation about diagonal BD.

In a quadrilateral only two deflations are possible: one uses diagonal AC and the other diagonal BD. As long as the quadrilateral remains simple we are permitted to perform deflations. Therefore deflations only come to a halt if all the deflations possible at the next step would result in a non-simple (self-intersecting) quadrilateral. We now show that all quadrilaterals that satisfy conditions (1) and (2) are simple. Therefore the quadrilateral admits infinitely many deflations.

The only way for a quadrilateral ABCD to become non-simple is if a pair of opposite edges intersect. We will show that this is impossible. Refer to Figures 3 and 4. The convex Figure 2. (a) Any square is already deflated (b) A kite is deflated with at most one deflation when C goes to C′

Figure 3. AD crosses BC implying AD + BC > AB + CD

hull of the vertices forms a convex quadrilateral. A well known fundamental property of convex quadrilaterals, that follows immediately from the triangle inequality, is that the sum of their diagonals is greater than the sum of a pair of opposite sides [8]. Therefore if a deflation results in AD properly crossing BC as in Figure 3 at point x then AD + BC is greater than AB + CD, which contradicts condition (1). On the other hand, if a deflation results in CD crossing AB as in Figure 4 at point x then AD + BC is less than AB + CD, which also contradicts condition (1). These arguments continue to hold if a deflation causes a vertex to fall on an edge of the polygon.

Furthermore, the above arguments also imply that the inequality becomes equality only if after a deflation either B falls on D or C falls on A, but this cannot happen as it would violate condition (2).

3. Ramifications

Our results have some immediate corollaries to related work. There has been interest recently in deflating and convexifying simple polygons using only ear-flips and mouth-flips, respectively. Let u, v, w be three consecutive vertices of a polygon P such that the angle at v is not equal to π. If v forms a convex vertex of P and all the vertices of P other than u, v, w lie in the exterior of triangle u, v, w, then u, v, w is an ear of P [6]. On the other hand, if v forms a concave vertex of P and all the vertices of P other than u, v, w lie in the exterior of triangle u, v, w, then u, v, w is a mouth of P [9]. An ear-flip reflects an ear u, v, w across the line determined by u, w while maintaining the simplicity of the resulting polygon. A mouth-flip reflects a mouth u, v, w across the line determined by u, w while maintaining the simplicity

Figure 4. CD crosses AB implying AD + BC < AB + CD

Figure 5. The pentagon ADEF B (star-shaped from A) does not admit a single mouth-flip

of the resulting polygon.

Millet [7] showed that equilateral star-shaped polygons (all edges of equal length) can be convexified with a finite number of mouth-flips and it was pointed out in [10] that in fact n! mouth-flips suffice. It is also known [3] that there exist non-equilateral star-shaped polygons that do not admit any mouth-flips. Another such example is shown in Figure 5. ABCD is a quadrilateral satifying conditions (1) and (2). Imagine flipping the mouth C to F, deleting edge DF and adding edges DE and EF to obtain a polygon ADEF B star-shaped from A. Flipping the mouth A would cause edge AB to intersect edge EF.

We can also construct a (non-equilateral) star-shaped polygon in which mouth-flips go on forever. Consider the same quadrilateral ABCD of Figure 5 but now delete edge AD and add edges AE and DE to obtain the star-shaped polygon ABCDE in Figure 6. Mouth flips now go on forever alternating at B and C without either ever reaching the segment AD.

Figure 6. In the pentagon ABCDE (star-shaped from B) mouth-flips go on forever 4. Concluding remarks

More generally, we have also determined necessary and sufficient conditions for any simple polygon to admit infinitely many deflations. However, these results will be described in a future paper.

References

[1] Biedl, T.; Demaine, E.; Demaine, M.; Lazard, S.; Lubiw, A.; O’Rourke, J.; Overmars, M.; Robbins, S.; Streinu, I.; Toussaint, G. T.; Whitesides, S.: Locked and unlocked polygonal chains in 3d. In: Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999, 866–867.

[2] de Sz.-Nagy, Béla: Solution of problem 3763. American Mathematical Monthly 46 (1939), 176–177.

[3] Díaz-Bánez, J. M.; Gomez, F.; Toussaint, G. T.: Partial deflation of closed polygons in the plane. Manuscript in preparation, 1999.

[4] Erdős, Paul: Problem number 3763. American Mathematical Monthly 42 (1935), 627.

[5] Grünbaum, Branko: How to convexify a polygon. Geombinatorics 5 (1995), 24–30.

[6] Meisters, Gary H.: Polygons have ears. American Mathematical Monthly 82 (1975), 648–651.

[7] Millett, K.: Knotting of regular polygons in 3-space. Journal of Knot Theory and its Ramifications 3 (1994), 263–278.

[8] Quintas, L. V.; Supnick, F.: On some properties of shortest hamiltonian circuits. American Mathematical Monthly 72 (1965), 977–980.

[9] Toussaint, Godfried T.: Anthropomorphic polygons. American Mathematical Monthly 98 (1991), 31–35.

[10] Toussaint, Godfried T.: The Erdős-Nagy theorem and its ramifications. In: 11th Canadian Conference on Computational Geometry. Vancouver, Canada, August 16–18 1999, 9–12. Long version available at: http://www.cs.ubc.ca/conferences/CCCG.

[11] Wegner, Bernd: Partial inflation of closed polygons in the plane. Beiträge Algebra Geom. 34(1) (1993), 77–85.

Received August 1, 2000