Document Open Access Logo

The Geodesic Edge Center of a Simple Polygon

Authors Anna Lubiw , Anurag Murty Naredla

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.49.pdf
  • Filesize: 0.82 MB
  • 15 pages

Document Identifiers

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
  • Institut für Informatik, University of Bonn, Bonn, Germany

Funding

Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).

Acknowledgements

For helpful comments we thank Boris Aronov, Therese Biedl, John Hershberger, Joseph Mitchell, and the SoCG reviewers.

Cite As Get BibTex

Anna Lubiw and Anurag Murty Naredla. The Geodesic Edge Center of a Simple Polygon. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.49

Abstract

The geodesic edge center of a polygon is a point c inside the polygon that minimizes the maximum geodesic distance from c to any edge of the polygon, where geodesic distance is the shortest path distance inside the polygon. We give a linear-time algorithm to find a geodesic edge center of a simple polygon. This improves on the previous O(n log n) time algorithm by Lubiw and Naredla [European Symposium on Algorithms, 2021]. The algorithm builds on an algorithm to find the geodesic vertex center of a simple polygon due to Pollack, Sharir, and Rote [Discrete & Computational Geometry, 1989] and an improvement to linear time by Ahn, Barba, Bose, De Carufel, Korman, and Oh [Discrete & Computational Geometry, 2016].
The geodesic edge center can easily be found from the geodesic farthest-edge Voronoi diagram of the polygon. Finding that Voronoi diagram in linear time is an open question, although the geodesic nearest edge Voronoi diagram (the medial axis) can be found in linear time. As a first step of our geodesic edge center algorithm, we give a linear-time algorithm to find the geodesic farthest-edge Voronoi diagram restricted to the polygon boundary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • geodesic center of polygon
  • farthest edges
  • farthest-segment Voronoi diagram

Metrics

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

Related Versions

References

  1. Alok Aggarwal, Maria M Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1-4):195-208, 1987. URL: https://doi.org/10.1007/bf01840359.
  2. 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.
  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.1007/bf02189321.
  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. 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: https://doi.org/10.4230/LIPIcs.SoCG.2019.12.
  6. 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.
  7. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete & Computational Geometry, 9(2):145-158, 1993. URL: https://doi.org/10.1007/bf02189314.
  8. Bernard Chazelle and Jiří Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms, 21(3):579-597, 1996. URL: https://doi.org/10.1006/jagm.1996.0060.
  9. Francis Chin, Jack Snoeyink, and Cao An Wang. Finding the medial axis of a simple polygon in linear time. Discrete & Computational Geometry, 21(3):405-420, 1999. URL: https://doi.org/10.1007/pl00009429.
  10. R L Scot Drysdale and Asish Mukhopadhyay. An O(n log n) algorithm for the all-farthest-segments problem for a planar set of points. Information Processing Letters, 105(2):47-51, 2008. URL: https://doi.org/10.1016/j.ipl.2007.08.004.
  11. Martin E Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing, 13(1):31-45, 1984. URL: https://doi.org/10.1137/0213003.
  12. Sariel Har-Peled. Geometric Approximation Algorithms. American Mathematical Society, 2011. URL: https://doi.org/10.1090/surv/173.
  13. John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. URL: https://doi.org/10.1137/s0097539793253577.
  14. Elena Khramtcova and Evanthia Papadopoulou. An expected linear-time algorithm for the farthest-segment Voronoi diagram. arXiv, 2014. URL: https://doi.org/10.48550/arxiv.1411.2816.
  15. Anna Lubiw and Anurag Murty Naredla. The visibility center of a simple polygon. arXiv, 2021. URL: https://doi.org/10.48550/arxiv.2108.07366.
  16. Anna Lubiw and Anurag Murty Naredla. The visibility center of a simple polygon. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 65:1-65:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.65.
  17. Anna Lubiw and Anurag Murty Naredla. The geodesic edge center of a simple polygon. arXiv, 2023. URL: https://doi.org/10.48550/arXiv.2303.09702.
  18. Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer Verlag, 2002. URL: https://doi.org/10.1007/978-1-4613-0039-7.
  19. 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.
  20. Nimrod Megiddo. On the ball spanned by balls. Discrete & Computational Geometry, 4(6):605-610, 1989. URL: https://doi.org/10.1007/bf02187750.
  21. Nabil H Mustafa. Sampling in Combinatorial and Geometric Set Systems, volume 265 of Mathematical Surveys and Monographs. American Mathematical Society, 2022. URL: https://doi.org/10.1090/surv/265.
  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. URL: https://doi.org/10.1007/s00454-019-00063-4.
  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. Evanthia Papadopoulou and Sandeep Kumar Dey. On the farthest line-segment Voronoi diagram. International Journal of Computational Geometry & Applications, 23(06):443-459, 2013. URL: https://doi.org/10.1007/978-3-642-35261-4_22.
  25. 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.
  26. Michael Ian Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (FOCS 1975), pages 151-162. IEEE, 1975. URL: https://doi.org/10.1109/sfcs.1975.8.
  27. Subhash Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences, 39:220-235, 1989. URL: https://doi.org/10.1016/0022-0000(89)90045-7.
  28. Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman, editors. Handbook of Discrete and Computational Geometry. CRC press, 2017. URL: https://doi.org/10.1201/9781315119601.
  29. Haitao Wang. An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons. Discrete & Computational Geometry, 2022. URL: https://doi.org/10.1007/s00454-022-00424-6.
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