×

zbMATH — the first resource for mathematics

Convexifying monotone polygons while maintaining internal visibility. (English) Zbl 1375.68118
Márquez, Alberto (ed.) 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: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 98-108 (2012).
Summary: 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 [E. D. Demaine and J. O’Rourke, “Open problems from CCCG 2008”, in: Proceedings of the 21st Canadian conference on computational geometry, CCCG’09. Vancouver: University of British Columbia. 75–78 (2009), http://cccg.ca/proceedings/2009/cccg09_20.pdf; S. L. Devadoss et al., “Visibility graphs and deformations of associahedra”, Preprint, arXiv:0903.2848]: (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.
For the entire collection see [Zbl 1253.68016].

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ábrego, B.M., Cetina, M., Leaños, J., Salazar, G.: Visibility-preserving convexifications using single-vertex moves. Information Processing Letters 112(5), 161–163 (2012) · Zbl 1237.68234 · doi:10.1016/j.ipl.2011.11.012
[2] Aichholzer, O., Aloupis, G., Demaine, E.D., Demaine, M.L., Dujmović, V., Hurtado, F., Lubiw, A., Rote, G., Schulz, A., Souvaine, D.L., Winslow, A.: Convexifying Polygons Without Losing Visibilities. In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pp. 229–234 (2011)
[3] Aichholzer, O., Cortes, C., Demaine, E.D., Dujmović, V., Erickson, J., Meijer, H., Overmars, M., Palop, B., Ramaswami, S., Toussaint, G.: Flipturning polygons. Discrete and Computational Geometry 28, 231–253 (2002) · Zbl 1011.68146 · doi:10.1007/s00454-002-2775-7
[4] Aloupis, G., Ballinger, B., Bose, P., Damian, M., Demaine, E.D., Demaine, M.L., Flatland, R.Y., Hurtado, F., Langerman, S., O’Rourke, J., Taslakian, P., Toussaint, G.T.: Vertex Pops and Popturns. In: Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), pp. 137–140 (2007)
[5] Biedl, T.C., Demaine, E.D., Lazard, S., Robbins, S.M., Soss, M.A.: Convexifying Monotone Polygons. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol. 1741, pp. 415–424. Springer, Heidelberg (1999) · Zbl 0964.68140 · doi:10.1007/3-540-46632-0_42
[6] Demaine, E.D., Gassend, B., O’Rourke, J., Toussaint, G.T.: All polygons flip finitely... right? In: Surveys on Discrete and Computational Geometry. Contemp. Math., vol. 453, pp. 231–255 (2008) · doi:10.1090/conm/453/08801
[7] Demaine, E.D., Langerman, S.: Personal communication, Montreal (2008)
[8] Demaine, E.D., O’Rourke, J.: Open Problems from CCCG 2008. In: Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), pp. 75–78 (2009)
[9] Devadoss, S.L., Shah, R., Shao, X., Winston, E.: Visibility graphs and deformations of associahedra, arXiv: 0903.2848 (March 2009) · Zbl 1317.52018
[10] Erdos, P.: Problem 3763. Amer. Math. Monthly 42, 627, 463–470 (1935)
[11] Grünbaum, B.: How to convexify a polygon. Geocombinatorics 5, 24–30 (1995) · Zbl 0866.52001
[12] de Sz.-Nagy, B.: Solution of problem 3763. Amer. Math. Monthly 49, 176–177 (1939)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.