Document Open Access Logo

Convex Hulls in Polygonal Domains

Authors Luis Barba, Michael Hoffmann , Matias Korman, Alexander Pilz

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.8.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Author Details

Luis Barba
  • Department of Computer Science, ETH Zürich, Zürich, Switzerland
Michael Hoffmann
  • Department of Computer Science, ETH Zürich, Zürich, Switzerland
Matias Korman
  • Tohoku University, Sendai, Japan
Alexander Pilz
  • Department of Computer Science, ETH Zürich. Zürich, Switzerland

Funding

  • Korman, Matias: Supported in part by MEXT KAKENHI Nos. 17K12635, 15H02665, and 24106007.
  • Pilz, Alexander: Supported by a Schrödinger fellowship of the Austrian Science Fund (FWF): J-3847-N35.

Cite As Get BibTex

Luis Barba, Michael Hoffmann, Matias Korman, and Alexander Pilz. Convex Hulls in Polygonal Domains. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.8

Abstract

We study generalizations of convex hulls to polygonal domains with holes. Convexity in Euclidean space is based on the notion of shortest paths, which are straight-line segments. In a polygonal domain, shortest paths are polygonal paths called geodesics. One possible generalization of convex hulls is based on the "rubber band" conception of the convex hull boundary as a shortest curve that encloses a given set of sites. However, it is NP-hard to compute such a curve in a general polygonal domain. Hence, we focus on a different, more direct generalization of convexity, where a set X is geodesically convex if it contains all geodesics between every pair of points x,y in X. The corresponding geodesic convex hull presents a few surprises, and turns out to behave quite differently compared to the classic Euclidean setting or to the geodesic hull inside a simple polygon. We describe a class of geometric objects that suffice to represent geodesic convex hulls of sets of sites, and characterize which such domains are geodesically convex. Using such a representation we present an algorithm to construct the geodesic convex hull of a set of O(n) sites in a polygonal domain with a total of n vertices and h holes in O(n^3h^{3+epsilon}) time, for any constant epsilon > 0.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • geometric graph
  • polygonal domain
  • geodesic hull
  • shortest path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Matias Korman, and Eunjin Oh. A linear-time algorithm for the geodesic center of a simple polygon. Discrete Comput. Geom., 56(4):836-859, 2016. Google Scholar
  2. Oswin Aichholzer, Matias Korman, Alexander Pilz, and Birgit Vogtenhuber. Geodesic order types. Algorithmica, 70(1):112-128, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9818-8.
  3. Sang Won Bae, Matias Korman, and Yoshio Okamoto. The geodesic diameter of polygonal domains. Discrete Comput. Geom., 50(2):306-329, 2013. Google Scholar
  4. Sang Won Bae, Matias Korman, and Yoshio Okamoto. Computing the geodesic centers of a polygonal domain. In Proc. 26th Canadian Conf. on Computational Geometry, 2014. Google Scholar
  5. Sang Won Bae and Yoshio Okamoto. Querying two boundary points for shortest paths in a polygonal domain. Comput. Geom., 45(7):284-293, 2012. URL: http://dx.doi.org/10.1016/j.comgeo.2012.01.012.
  6. Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, and Michiel H. M. Smid. Plane geodesic spanning trees, hamiltonian cycles, and perfect matchings in a simple polygon. Comput. Geom., 57:27-39, 2016. URL: http://dx.doi.org/10.1016/j.comgeo.2016.05.004.
  7. Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin. Geodesic ham-sandwich cuts. Discrete & Computational Geometry, 37(3):325-339, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1287-2.
  8. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1655-1670. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.110.
  9. Yi-Jen Chiang and Joseph S. B. Mitchell. Two-point Euclidean shortest path queries in the plane. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999. Google Scholar
  10. Mark de Berg. Translating polygons with applications to hidden surface removal. In John R. Gilbert and Rolf G. Karlsson, editors, SWAT 90, 2nd Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 11-14, 1990, Proceedings, volume 447 of Lecture Notes in Computer Science, pages 60-70. Springer, 1990. URL: http://dx.doi.org/10.1007/3-540-52846-6_78.
  11. Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark H. Overmars, and Sue Whitesides. Separating point sets in polygonal environments. Int. J. Comput. Geometry Appl., 15(4):403-420, 2005. URL: http://dx.doi.org/10.1142/S0218195905001762.
  12. Peter Eades and David Rappaport. The complexity of computing minimum separating polygons. Pattern Recognition Letters, 14(9):715-718, 1993. URL: http://dx.doi.org/10.1016/0167-8655(93)90140-9.
  13. Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126-152, 1989. Google Scholar
  14. John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM J. Comput., 26(6):1612-1634, 1997. Google Scholar
  15. John Hershberger and Subhash Suri. An optimal algorithm for euclidean shortest paths in the plane. SIAM J. Comput., 28(6):2215-2256, 1999. URL: http://dx.doi.org/10.1137/S0097539795289604.
  16. Anna Lubiw, Daniela Maftuleac, and Megan Owen. Shortest paths and convex hulls in 2d complexes with non-positive curvature. CoRR, abs/1603.00847, 2016. URL: http://arxiv.org/abs/1603.00847.
  17. Joseph S. B. Mitchell. Shortest paths and networks. In Handbook of Discrete and Computational Geometry, Second Edition. Chapman and Hall/CRC, 2004. Google Scholar
  18. Joseph S. B. Mitchell, Günter Rote, and Gerhard J. Woeginger. Minimum-link paths among obstacles in the plan. Algorithmica, 8(5&6):431-459, 1992. URL: http://dx.doi.org/10.1007/BF01758855.
  19. Micha Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom., 12(3):327-345, 1994. Google Scholar
  20. Godfried T. Toussaint. Computing geodesic properties inside a simple polygon. Revue D'Intelligence Artificielle, 3(2):9-42, 1989. Google Scholar
  21. Haitao Wang. On the geodesic centers of polygonal domains. In Proc. 24rd Annual European Symposium on Algorithms, volume 57 of LIPIcs, pages 77:1-77:17, 2016. Google Scholar
  22. Emo Welzl. Constructing the visibility graph for n-line segments in o(n²) time. Inf. Process. Lett., 20(4):167-171, 1985. URL: http://dx.doi.org/10.1016/0020-0190(85)90044-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact