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 {p1, p2, . . . , pn} of points (the vertices), plus the
straight segments (the edges) joining pi to pi+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
p1, p2, . . . , pn and q1, q2, . . . , qn 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σ{maxi∈{1,2,...,n}{∥pi −qσ(i)∥}}, where the minimum is taken over
all bijections σ : {1, 2, . . ., n} →{1, 2, . . ., n}.
Let Pn denote the collection of all polygons on n vertices. If P ∈Pn and δ > 0,
we let Nδ(P) denote the set of polygons Q ∈Pn 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→pt such
that pa = 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
Pn, 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 ∈Pn be a polygon with vertices p1, p2, . . . , pn. 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 ps
i and ps
j are P s-visible, then pt
i and pt
j are P t-visible. If in addition there exist
i, j ∈{1, 2, . . . , n} such that pa
i is not P a-visible from pa
j , but pd
i is P d-visible from
pd
j, then the transformation is visibility-increasing.
Let k ≥3. A k-tuple (q1, q2, . . . , qk) of vertices of a polygon P is critical if there
is a straight segment that contains q1, q2, . . . , qk, 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 ∈Pn, and let p1, p2, . . . , pn 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 Pn 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, pa+ℓτ
i
to pa+(ℓ+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 pb
i to-
wards pc
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