Document Open Access Logo

A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

Authors Hee Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Matias Korman, Eunjin Oh

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.209.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Hee Kap Ahn
Luis Barba
Prosenjit Bose
Jean-Lou De Carufel
Matias Korman
Eunjin Oh

Cite As Get BibTex

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. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 209-223, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.209

Abstract

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an O(n log n)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.

Subject Classification

Keywords
  • Geodesic distance
  • facility location
  • 1-center problem
  • simple polygons

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. CoRR, abs/1501.00561, 2015. Google Scholar
  2. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic Voronoi diagram. Discrete & Computational Geometry, 9(1):217-255, 1993. Google Scholar
  3. T. Asano and G.T. Toussaint. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, 1985. Google Scholar
  4. Sang Won Bae, Matias Korman, and Yoshio Okamoto. The geodesic diameter of polygonal domains. Discrete & Computational Geometry, 50(2):306-329, 2013. Google Scholar
  5. Sang Won Bae, Matias Korman, and Yoshio Okamoto. Computing the geodesic centers of a polygonal domain. In Proceedings of CCCG, 2014. Google Scholar
  6. Sang Won Bae, Matias Korman, Yoshio Okamoto, and Haitao Wang. Computing the L₁ geodesic diameter and center of a simple polygon in linear time. In Proceedings of LATIN, pages 120-131, 2014. Google Scholar
  7. Bernard Chazelle. A theorem on polygon cutting with applications. In Proceedings of FOCS, pages 339-349, 1982. Google Scholar
  8. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(1):485-524, 1991. Google Scholar
  9. H.N. Djidjev, A. Lingas, and J.-R. Sack. An O(nlog n) algorithm for computing the link center of a simple polygon. Discrete & Computational Geometry, 8:131-152, 1992. Google Scholar
  10. Herbert Edelsbrunner and Ernst Peter Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. on Graphics, 9(1):66-104, 1990. Google Scholar
  11. 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. Google Scholar
  12. 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. Google Scholar
  13. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  14. John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. Google Scholar
  15. Y. Ke. An efficient algorithm for link-distance problems. In Proceedings of SoCG, pages 69-78, 1989. Google Scholar
  16. Der-Tsai Lee and Franco P Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393-410, 1984. Google Scholar
  17. Jiří Matoušek. Approximations and optimal geometric divide-and-conquer. Journal of Computer and System Sciences, 50(2):203-208, 1995. Google Scholar
  18. Jiří Matoušek. Construction of epsilon nets. In Proc. of SoCG, pages 1-10. ACM, 1989. Google Scholar
  19. Nimrod Megiddo. On the ball spanned by balls. Discrete & Computational Geometry, 4(1):605-610, 1989. Google Scholar
  20. J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633-701. Elsevier, 2000. Google Scholar
  21. B.J. Nilsson and S. Schuierer. Computing the rectilinear link diameter of a polygon. In Proceedings of CG, pages 203-215, 1991. Google Scholar
  22. B.J. Nilsson and S. Schuierer. An optimal algorithm for the rectilinear link center of a rectilinear polygon. Computational Geometry: Theory and Applications, 6:169-194, 1996. Google Scholar
  23. Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete & Computational Geometry, 4(1):611-626, 1989. Google Scholar
  24. S. Suri. Minimum Link Paths in Polygons and Related Problems. PhD thesis, Johns Hopkins Univ., 1987. Google Scholar
  25. Subhash Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences, 39(2):220-235, 1989. Google Scholar
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