Document Open Access Logo

The Visibility Center of a Simple Polygon

Authors Anna Lubiw, Anurag Murty Naredla

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2021.65.pdf
  • Filesize: 1.74 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Visibility
  • Shortest Paths
  • Simple Polygons
  • Facility Location

Metrics

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

Abstract

We introduce the visibility center of a set of points inside a polygon - a point c_V such that the maximum geodesic distance from c_V to see any point in the set is minimized. For a simple polygon of n vertices and a set of m points inside it, we give an O((n+m) log (n+m)) time algorithm to find the visibility center. We find the visibility center of all points in a simple polygon in O(n log n) time.
Our algorithm reduces the visibility center problem to the problem of finding the geodesic center of a set of half-polygons inside a polygon, which is of independent interest. We give an O((n+k) log (n+k)) time algorithm for this problem, where k is the number of half-polygons.

Cite As Get BibTex

Anna Lubiw and Anurag Murty Naredla. The Visibility Center of a Simple Polygon. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.65

Author Details

Anna Lubiw
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Anurag Murty Naredla
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada

Funding

  • Lubiw, Anna: Supported by NSERC.

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 & Computational Geometry, 56(4):836-859, 2016. URL: https://doi.org/10.1007/s00454-016-9796-0.
  2. Esther M Arkin, Alon Efrat, Christian Knauer, Joseph S.B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie. Shortest path to a segment and quickest visibility queries. Journal of Computational Geometry, 7:77-100, 2016. URL: https://jocg.org/index.php/jocg/article/view/3001.
  3. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic Voronoi diagram. Discrete & Computational Geometry, 9(3):217-255, 1993. URL: https://doi.org/10.1145/73393.73417.
  4. Franz Aurenhammer, Robert L Scot Drysdale, and Hannes Krasser. Farthest line segment Voronoi diagrams. Information Processing Letters, 100(6):220-225, 2006. URL: https://doi.org/10.1016/j.ipl.2006.07.008.
  5. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, 2013. Google Scholar
  6. Luis Barba. Optimal algorithm for geodesic farthest-point Voronoi diagrams. In 35th International Symposium on Computational Geometry (SoCG 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: http://drops.dagstuhl.de/opus/volltexte/2019/10416.
  7. Binay K Bhattacharya, Shreesh Jadhav, Asish Mukhopadhyay, and J-M Robert. Optimal algorithms for some intersection radius problems. Computing, 52(3):269-279, 1994. URL: https://doi.org/10.1007/bf02246508.
  8. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(3):485-524, 1991. URL: https://doi.org/10.1007/bf02574703.
  9. Wei-Pang Chin and Simeon Ntafos. Shortest watchman routes in simple polygons. Discrete & Computational Geometry, 6(1):9-31, 1991. URL: https://doi.org/10.1007/bf02574671.
  10. Hristo N Djidjev, Andrzej Lingas, and Jörg-Rüdiger Sack. An O(n log n) algorithm for computing the link center of a simple polygon. Discrete & Computational Geometry, 8(2):131-152, 1992. Google Scholar
  11. Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph SB Mitchell. Touring a sequence of polygons. In Proceedings of the thirty-fifth Annual ACM Symposium on Theory of Computing (STOC '03, pages 473-482, 2003. URL: https://doi.org/10.1145/780542.780612.
  12. Subir Kumar Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, 2007. Google Scholar
  13. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209-233, 1987. URL: https://doi.org/10.1007/bf01840360.
  14. Leonidas J Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. URL: https://doi.org/10.1016/0022-0000(89)90041-x.
  15. David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete & Computational Geometry, 2(2):127-151, 1987. Google Scholar
  16. John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms, 18(3):403-431, 1995. URL: https://doi.org/10.1006/jagm.1995.1017.
  17. Shreesh Jadhav, Asish Mukhopadhyay, and Binay Bhattacharya. An optimal algorithm for the intersection radius of a set of convex polygons. Journal of Algorithms, 20(2):244-267, 1996. Google Scholar
  18. Yan Ke and Joseph O'Rourke. Computing the kernel of a point set in a polygon. In Workshop on Algorithms and Data Structures, pages 135-146. Springer, 1989. Google Scholar
  19. Der-Tsai Lee and Franco P Preparata. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM (JACM), 26(3):415-421, 1979. URL: https://doi.org/10.1145/322139.322142.
  20. Nimrod Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. URL: https://doi.org/10.1137/0212052.
  21. Nimrod Megiddo. On the ball spanned by balls. Discrete & Computational Geometry, 4(6):605-610, 1989. URL: https://doi.org/10.1007/bf02187750.
  22. Eunjin Oh and Hee-Kap Ahn. Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discrete & Computational Geometry, 63(2):418-454, 2020. Google Scholar
  23. Eunjin Oh, Luis Barba, and Hee-Kap Ahn. The geodesic farthest-point Voronoi diagram in a simple polygon. Algorithmica, 82(5):1434-1473, 2020. URL: https://doi.org/10.1007/s00453-019-00651-z.
  24. Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete & Computational Geometry, 4(6):611-626, 1989. URL: https://doi.org/10.1007/bf02187751.
  25. Godfried T Toussaint. Computing geodesic properties inside a simple polygon. Revue d'Intelligence Artificielle, 3(2):9-42, 1989. Google Scholar
  26. Haitao Wang. Quickest visibility queries in polygonal domains. Discrete & Computational Geometry, 62(2):374-432, 2019. URL: https://doi.org/10.1007/s00454-019-00108-8.
  27. Haitao Wang. An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons. In International Symposium on Computational Geometry (SoCG 2021), 2021. URL: https://arxiv.org/pdf/2103.00076.pdf.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact