Document Open Access Logo

On the Geodesic Centers of Polygonal Domains

Author Haitao Wang

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.77.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Haitao Wang

Cite AsGet BibTex

Haitao Wang. On the Geodesic Centers of Polygonal Domains. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 77:1-77:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.77

Abstract

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain P of n vertices. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of P that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the size of the shortest path map equivalence decomposition of P, which is known to be O(n^{10}). One key observation is a pi-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in O(n^{11}*log(n)) time. Previously, an algorithm of O(n^{12+epsilon}) time was known for this problem, for any epsilon > 0.
Keywords
  • geodesic centers
  • shortest paths
  • polygonal domains

Metrics

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

References

  1. H.-K. Ahn, L. Barba, P. Bose, J.-L. De Carufel, M. Korman, and E. Oh. A linear-time algorithm for the geodesic center of a simple polygon. In Proc. of the 31st Annual Symposium on Computational Geometry (SoCG), pages 209-223, 2015. Google Scholar
  2. T. Asano and G. Toussaint. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, Montreal, Canada, 1985. Google Scholar
  3. S.W. Bae, M. Korman, and Y. Okamoto. The geodesic diameter of polygonal domains. Discrete and Computational Geometry, 50:306-329, 2013. Google Scholar
  4. S.W. Bae, M. Korman, and Y. Okamoto. Computing the geodesic centers of a polygonal domain. In Proc. of the 26th Canadian Conference on Computational Geometry (CCCG), 2014. Google Scholar
  5. S.W. Bae, M. Korman, Y. Okamoto, and H. Wang. Computing the L₁ geodesic diameter and center of a simple polygon in linear time. Computational Geometry: Theory and Applications, 48:495-505, 2015. Google Scholar
  6. B. Chazelle. A theorem on polygon cutting with applications. In Proc. of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 339-349, 1982. Google Scholar
  7. Y.-J. Chiang and J.S.B. Mitchell. Two-point Euclidean shortest path queries in the plane. In Proc. of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 215-224, 1999. Google Scholar
  8. H.N. Djidjev, A. Lingas, and J.-R. Sack. An O(nlog n) algorithm for computing the link center of a simple polygon. Discrete and Computational Geometry, 8:131-152, 1992. Google Scholar
  9. H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317-340, 1986. Google Scholar
  10. D. Halperin and M. Sharir. New bounds for lower envelopes in three dimensions, with applications to visibility in terrains. Discrete and Computational Geometry, 12:313-326, 1994. Google Scholar
  11. J. Hershberger and S. Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. Google Scholar
  12. J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing, 28(6):2215-2256, 1999. Google Scholar
  13. Y. Ke. An efficient algorithm for link-distance problems. In Proc. of the 5th Annual Symposium on Computational Geometry (SoCG), pages 69-78, 1989. Google Scholar
  14. D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, 1983. Google Scholar
  15. J.S.B. Mitchell. Geometric shortest paths and network optimization, in Handbook of Computational Geometry, J.-R Sack and J. Urrutia (eds.), pages 633-702. Elsevier, Amsterdam, the Netherlands, 2000. Google Scholar
  16. B.J. Nilsson and S. Schuierer. Computing the rectilinear link diameter of a polygon. In Proc. of the International Workshop on Computational Geometry - Methods, Algorithms and Applications, pages 203-215, 1991. Google Scholar
  17. 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
  18. R. Pollack, M. Sharir, and G. Rote. Computing the geodesic center of a simple polygon. Discrete and Computational Geometry, 4(1):611-626, 1989. Google Scholar
  19. S. Schuierer. An optimal data structure for shortest rectilinear path queries in a simple rectilinear polygon. International Journal of Compututational Geometry and Applications, 6:205-226, 1996. Google Scholar
  20. S. Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences, 39: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 Imprint Privacy Contact