arXiv:1105.3435v1 [cs.CG] 17 May 2011  VISIBILITY-PRESERVING CONVEXIFICATIONS USING SINGLE-VERTEX MOVES  B.M.  ́ ABREGO, M. CETINA, J. LEA  ̃ NOS, AND G. SALAZAR  Abstract.   Devadoss asked: (1) can every polygon be convexified so that no internal visibility (between vertices) is lost in the process? Moreover, (2) does such a convexification exist, in which exactly one vertex is moved at a time (that is, using   single-vertex moves )? We prove the redundancy of the “single- vertex moves” condition:   an affirmative answer to (1) implies an affirmative answer to (2). Since Aichholzer et al. recently proved (1), this settles (2).  1.   Introduction  The problem of   convexifying   a polygon (that is, continuously transforming it, while maintaining simplicity) is a classical, well-studied problem in computational geometry. Different restrictions on the transformations allowed give rise to several versions of this problem. In the most famous variant, the lengths of the edges are to be maintained; this is the celebrated Carpenter’s Rule Theorem (see [3, 6]). Devadoss [4] proposed another variant:   (1) can every polygon be convexified without losing internal visibility between any pair of vertices? (equivalently: does every polygon admit a   visibility-preserving   convexification?)   Devadoss [5] also raised a stronger version of this question: (2) does there exist a visibility-preserving convexification in which at most one vertex is moved at a time (that is, by   single- vertex moves )? Partial answers to (1) and (2) were given in [2] and [5]. Our main result is the following.  Theorem 1.   An affirmative answer to (1) implies an affirmative answer to (2). That is: if every polygon has a visibility-preserving convexification, then every poly- gon has a visibility-preserving convexification using only single-vertex moves.  Since (1) has been recently settled in the afirmative by Aichholzer et al. [1], we have the following.  Corollary 2.   Every polygon has a visibility-preserving convexification using only single-vertex moves.     In Section 2 we formalize the relevant notions at play (such as visibility-preserving transformations and single-vertex moves). The proof of Theorem 1 is in Section 3.  Date : October 15, 2018. 2010   Mathematics Subject Classification.   52A10, 52B55, 52C25, 68R01, 68U05.  Key words and phrases.   Convexification, visibility, visibility-maintaining, visibility-preserving, polygon, single-vertex moves. Supported by CONACYT grant 106432.  1
VISIBILITY-PRESERVING CONVEXIFICATIONS USING SINGLE-VERTEX MOVES   2  2.   Visibility, transformations, and single-vertex moves  A   polygon   consists of a finite set   { p 1 , p 2 , . . . , p n }   of points (the   vertices ), plus the straight segments (the   edges ) joining   p i   to   p i +1   for   i   = 1 ,   2 , . . . , n   (indices are read modulo   n ).   Throughout this work we implicitly assume that all polygons under consideration are   simple : edges only intersect in a common endpoint. Two points in   P   are   internally visible   (for brevity,   visible ) in   P   if the open segment joining them is contained in the interior of   P   . We also say that the points are   P   - visible . If  p, q   are   P   -visible vertices, then   { p, q }   is a   P   - visible pair . To speak meaningfully about the continuity of the transformations under con- sideration, first we must agree on the underlying metric.   Let   ‖ p   −   q ‖   denote the usual Euclidean distance between points   p   and   q .   Let   P, Q   be polygons, and let  p 1 , p 2 , . . . , p n   and   q 1 , q 2 , . . . , q n   be their respective vertices (distance is only defined between polygons with the same number of vertices). The   distance   d ( P, Q ) between  P   and   Q   is min σ { max i ∈{ 1 , 2 ,...,n } {‖ p i   −   q σ ( i ) ‖}} , where the minimum is taken over all bijections   σ   :   { 1 ,   2 , . . . , n } → { 1 ,   2 , . . . , n } . Let   P n   denote the collection of all polygons on   n   vertices. If   P   ∈   P n   and   δ >   0, we let   N δ   ( P   ) denote the set of polygons   Q   ∈   P n   such that   d ( P, Q )   < δ . The polygonal transformations under consideration are obtained by moving the vertices of the polygon; their incident edges get dragged along.   Thus, a trans- formation on a polygon   P   gets induced by defining, for each vertex   p   of   P   , a (time-parameterized) mapping that follows the movement of   p . The time domain is any closed interval [ a, d ], and the   orbit   of   p   is a continuous mapping   t   7   →   p t   such that   p a   =   p . Thus, for each   t   ∈   [ a, d ] we obtain a polygon   P   t   (where   P   a   =   P   ), and the transformation (which we denote   P   [ a,d ] ) is a continuous mapping from [ a, d ] to  P n , transforming the   initial   polygon   P   a   =   P   onto the   final   polygon   P   d . If   P   d   is convex, then the transformation is a   convexification   of   P   a   =   P   . If only one orbit is not the constant map, then the transformation is a   single-vertex move . Now let   P   ∈   P n   be a polygon with vertices   p 1 , p 2 , . . . , p n .   A transformation  P   [ a,d ]   on   P   is   visibility-preserving   if for all   i, j   ∈ { 1 ,   2 , . . . , n }   and all   a   ≤   s   ≤   t   ≤   d , if   p s i   and   p s j   are   P   s -visible, then   p t i   and   p t j   are   P   t -visible. If in addition there exist  i, j   ∈ { 1 ,   2 , . . . , n }   such that   p a i   is not   P   a -visible from   p a j   , but   p d i   is   P   d -visible from  p d j   , then the transformation is   visibility-increasing . Let   k   ≥   3. A   k -tuple ( q 1 , q 2 , . . . , q k ) of vertices of a polygon   P   is   critical   if there is a straight segment that contains   q 1 , q 2 , . . . , q k , and does not contain any point in the exterior of   P   . A polygon is   critical   if it contains a critical   k -tuple for some  k   ≥   3. The proof of the following is a trivial exercise.  Observation 3.   If   P   is a critical polygon, then there is a visibility-increasing single-vertex move with initial polygon   P   .     Let   P   be a polygon, and let   δ >   0 be small enough so that for every   Q   ∈   N δ   ( P   ), there is a unique natural bijection between the vertices of   P   and the vertices of   Q . We say that   δ   is a   safe radius   for   P   if for every   Q   ∈   N δ   ( P   ), a triple of vertices of  Q   is critical only if the corresponding triple in   P   is also critical. The proof of the following is straightforward.  Observation 4.   Every polygon has a safe radius.   
VISIBILITY-PRESERVING CONVEXIFICATIONS USING SINGLE-VERTEX MOVES   3  3.   Proof of Theorem 1  Let   P   ∈   P n , and let   p 1 , p 2 , . . . , p n   be the vertices of   P   .   With   n   fixed, we proceed by induction on the number of nonvisible pairs. Since adjacent vertices are not visible to each other, it follows that the minimum number of nonvisible pairs is   n . If there are exactly   n   nonvisible pairs, then   P   is convex, and there is nothing to prove. Thus we assume that   P   has   m > n   nonvisible pairs, and that the result holds for every polygon in   P n   with fewer than   m   nonvisible pairs. By assumption, there exists a visibility-preserving convexification   P   [ a,d ]   of   P   . An elementary real analysis argument shows that there exists a smallest   c   ∈   [ a, d ] such that   P   c   is critical. We note that if   c   =   a , then by Observation 3 we are done, using the induction hypothesis. Thus we may assume that   c > a . Since   t   7   →   P   t   is continuous for all   t   ∈   [ a, c ], Observation 4 and the compactness of [ a, c ] imply that there is a   δ >   0 that is a safe radius for   P   t   for every   t   ∈   [ a, c ]. A similar elementary continuity argument using the compactness of [ a, c ] shows that there exists a   τ >   0 such that, for all   s, t   ∈   [ a, c ] such that   | s −   t |   < τ   ,   d ( P   s , P   t )   < δ . Evidently, we may choose   τ   so that there is an integer   L   such that   c   −   a   =   Lτ   . Let   b   :=   c   −   τ   .   We claim that for   ℓ   = 0 ,   1 , . . . , L   −   2 there is a sequence of visibility-preserving single-vertex moves that takes   P   a + ℓτ   to   P   a +( ℓ +1) τ   .   Indeed, it suffices to move (in any order), for   i   = 1 ,   2 , . . . , n ,   p a + ℓτ i   to   p a +( ℓ +1) τ i   following the orbit   p [ a + ℓτ,a +( ℓ +1) τ   ]  i   .   The choice of   τ   guarantees that each of these moves is visibility-preserving. We conclude that there is a sequence of visibility-preserving single-vertex moves that takes   P   a   to   P   b . Once we reach   P   b   we proceed similarly towards   P   c , moving each vertex   p b i   to- wards   p c i   , one at a time, for   i   = 1 ,   2 , . . . , n .   Consider the first critical polygon   Q  reached in this last stage (such a   Q   obviously exists, since   P   c   itself is critical). Vis- ibility losses (respectively, gains) may occur only when (respectively, immediately after) reaching critical polygons. Thus, the choice of   Q   implies that before reaching  Q , we cannot have lost visibility. Suppose first that in the moment we reach   Q   we lose visibility; we shall derive a contradiction. In this case, the moving vertex (we recall we reach   Q   via a single- vertex move) must be part of a critical triple at   Q , and two of these vertices must lose visibility at the moment of reaching   Q .   Immediately before reaching   Q , the corresponding three vertices clearly satisfy the following (which we call   Property A ): each two of them are either a visible pair or adjacent. Since before reaching   Q   there is no loss of visibility, the corresponding three vertices in   P   b   (and hence all the way back to   P   a ) must also satisfy Property A. But the corresponding three vertices in  P   c   cannot satisfy Property A: indeed, the choice of   δ   and   τ   , plus the fact that they are a critical triple in   Q , imply that they must form a critical triple in   P   c , but no critical triple satisfies Property A. This implies that there is a pair of vertices that are   P   b -visible but not   P   c -visible, contradicting that   P   [ a,c ]   is visibility-preserving. Suppose finally that at the moment of reaching   Q   we do not lose visibility. In this case, we have then reached   Q   from   P   b   (and hence from   P   a   as well) by a sequence of visibility-preserving single-vertex moves. Since   Q   is critical, then we are done by Observation 3 and the induction hypothesis.   
VISIBILITY-PRESERVING CONVEXIFICATIONS USING SINGLE-VERTEX MOVES   4  References  [1] O. Aichholzer, G. Aloupis, E.D. Demaine, M.L. Demaine, V. Dujmovi ́ c, F. Hurtado, A. Lubiw, G. Rote, A. Schulz, D.L. Souvaine, and A. Winslow, Convexifying polygons without losing visibilities. Manuscript (2011). [2] O. Aichholzer, M. Cetina, R. Fabila, J. Lea ̃ nos, G. Salazar, and J. Urrutia, Convexifying monotone polygons while maintaining internal visibility. Manuscript (2011). [3] R. Connelly, E. D. Demaine and G. Rote,   Straightening polygonal arcs and convexifying polygonal cycles . Discrete Comput. Geom.   30   (2003), 205–239. [4] E. D. Demaine, J. O’Rourke, Open Problems from CCCG 2008. In   Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009) , 75–78. [5] S.L. Devadoss, R. Shah, X. Shao, and E. Winston, Visibility graphs and deformations of associahedra.   arXiv:0903.2848v1 [math.CO] . [6] I. Streinu,   Pseudo-triangulations, rigidity and motion planning . Discrete Comput. Geom.   34  (2005), 587-635.  Department of Mathematics, California State University. Northridge CA.  E-mail address :   bernardo.abrego@csun.edu  Instituto de F ́ ısica, UASLP. San Luis Potosi, Mexico.  E-mail address :   mcetina@ifisica.uaslp.mx  Unidad Acad ́ emica de Matem ́ aticas, UAZ. Zacatecas, Mexico.  E-mail address :   jleanos@mate.reduaz.mx  Instituto de F ́ ısica, UASLP. San Luis Potosi, Mexico.  E-mail address :   gsalazar@ifisica.uaslp.mx