Convexifying monotone polygons while maintaining internal visibility

Oswin Aichholzer; Mario Cetina; R. Fabila-Monroy; Jesús Leanos; Gelasio Salazar; Jorge Urrutia

doi:10.1007/978-3-642-34191-5_9

Convexifying monotone polygons while maintaining internal visibility

Oswin Aichholzer
, Mario Cetina
, R. Fabila-Monroy
, Jesús Leanos
, Gelasio Salazar
, Jorge Urrutia

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

Let P be a simple polygon on the plane. Two vertices of P are visible if the open line segment joining them is contained in the interior of P. In this paper we study the following questions posed in [8,9]: (1) Is it true that every non-convex simple polygon has a vertex that can be continuously moved such that during the process no vertex-vertex visibility is lost and some vertex-vertex visibility is gained? (2) Can every simple polygon be convexified by continuously moving only one vertex at a time without losing any internal vertex-vertex visibility during the process?

We provide a counterexample to (1). We note that our counterexample uses a monotone polygon. We also show that question (2) has a positive answer for monotone polygons.

Original language	English
Title of host publication	Computational Geometry
Subtitle of host publication	XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers
Place of Publication	Berlin; Heidelberg
Pages	98-108
DOIs	https://doi.org/10.1007/978-3-642-34191-5_9
Publication status	Published - 2012
Event	14th Spanish Meeting on Computational Geometry: EGC 2011 - Alcalá de Henares, Spain Duration: 27 Jun 2011 → 30 Jun 2011

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	7579

Conference

Conference	14th Spanish Meeting on Computational Geometry
Abbreviated title	EGC 2011
Country/Territory	Spain
City	Alcalá de Henares
Period	27/06/11 → 30/06/11

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-642-34191-5_9

Cite this

Aichholzer, O., Cetina, M., Fabila-Monroy, R., Leanos, J., Salazar, G., & Urrutia, J. (2012). Convexifying monotone polygons while maintaining internal visibility. In Computational Geometry : XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers (pp. 98-108). (Lecture Notes in Computer Science; Vol. 7579).. https://doi.org/10.1007/978-3-642-34191-5_9

Convexifying monotone polygons while maintaining internal visibility. / Aichholzer, Oswin; Cetina, Mario; Fabila-Monroy, R. et al.
Computational Geometry : XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers. Berlin; Heidelberg, 2012. p. 98-108 (Lecture Notes in Computer Science; Vol. 7579).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Aichholzer, O, Cetina, M, Fabila-Monroy, R, Leanos, J, Salazar, G & Urrutia, J 2012, Convexifying monotone polygons while maintaining internal visibility. in Computational Geometry : XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7579, Berlin; Heidelberg, pp. 98-108, 14th Spanish Meeting on Computational Geometry, Alcalá de Henares, Spain, 27/06/11. https://doi.org/10.1007/978-3-642-34191-5_9

Aichholzer O, Cetina M, Fabila-Monroy R, Leanos J, Salazar G, Urrutia J. Convexifying monotone polygons while maintaining internal visibility. In Computational Geometry : XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers. Berlin; Heidelberg. 2012. p. 98-108. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-34191-5_9

Aichholzer, Oswin ; Cetina, Mario ; Fabila-Monroy, R. et al. / Convexifying monotone polygons while maintaining internal visibility. Computational Geometry : XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers. Berlin; Heidelberg, 2012. pp. 98-108 (Lecture Notes in Computer Science).

@inproceedings{b85305c3e510479f88217ebf53b21bb8,

title = "Convexifying monotone polygons while maintaining internal visibility",

abstract = "Let P be a simple polygon on the plane. Two vertices of P are visible if the open line segment joining them is contained in the interior of P. In this paper we study the following questions posed in [8,9]: (1) Is it true that every non-convex simple polygon has a vertex that can be continuously moved such that during the process no vertex-vertex visibility is lost and some vertex-vertex visibility is gained? (2) Can every simple polygon be convexified by continuously moving only one vertex at a time without losing any internal vertex-vertex visibility during the process? We provide a counterexample to (1). We note that our counterexample uses a monotone polygon. We also show that question (2) has a positive answer for monotone polygons.",

author = "Oswin Aichholzer and Mario Cetina and R. Fabila-Monroy and Jes{\'u}s Leanos and Gelasio Salazar and Jorge Urrutia",

note = "In A. Marquez, P. Ramos, and J. Urrutia, editors, Special issue: XIV Encuentros de Geometr{\'i}a Computacional ECG2011; 14th Spanish Meeting on Computational Geometry : EGC 2011, EGC 2011 ; Conference date: 27-06-2011 Through 30-06-2011",

year = "2012",

doi = "10.1007/978-3-642-34191-5\_9",

language = "English",

isbn = "978-3-642-34190-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "98--108",

booktitle = "Computational Geometry",

}

TY - GEN

T1 - Convexifying monotone polygons while maintaining internal visibility

AU - Aichholzer, Oswin

AU - Cetina, Mario

AU - Fabila-Monroy, R.

AU - Leanos, Jesús

AU - Salazar, Gelasio

AU - Urrutia, Jorge

N1 - In A. Marquez, P. Ramos, and J. Urrutia, editors, Special issue: XIV Encuentros de Geometría Computacional ECG2011

PY - 2012

Y1 - 2012

N2 - Let P be a simple polygon on the plane. Two vertices of P are visible if the open line segment joining them is contained in the interior of P. In this paper we study the following questions posed in [8,9]: (1) Is it true that every non-convex simple polygon has a vertex that can be continuously moved such that during the process no vertex-vertex visibility is lost and some vertex-vertex visibility is gained? (2) Can every simple polygon be convexified by continuously moving only one vertex at a time without losing any internal vertex-vertex visibility during the process? We provide a counterexample to (1). We note that our counterexample uses a monotone polygon. We also show that question (2) has a positive answer for monotone polygons.

AB - Let P be a simple polygon on the plane. Two vertices of P are visible if the open line segment joining them is contained in the interior of P. In this paper we study the following questions posed in [8,9]: (1) Is it true that every non-convex simple polygon has a vertex that can be continuously moved such that during the process no vertex-vertex visibility is lost and some vertex-vertex visibility is gained? (2) Can every simple polygon be convexified by continuously moving only one vertex at a time without losing any internal vertex-vertex visibility during the process? We provide a counterexample to (1). We note that our counterexample uses a monotone polygon. We also show that question (2) has a positive answer for monotone polygons.

U2 - 10.1007/978-3-642-34191-5_9

DO - 10.1007/978-3-642-34191-5_9

M3 - Conference paper

SN - 978-3-642-34190-8

T3 - Lecture Notes in Computer Science

SP - 98

EP - 108

BT - Computational Geometry

CY - Berlin; Heidelberg

T2 - 14th Spanish Meeting on Computational Geometry

Y2 - 27 June 2011 through 30 June 2011

ER -

Convexifying monotone polygons while maintaining internal visibility

Abstract

Publication series

Conference

Fields of Expertise

Access to Document

Fingerprint

Cite this