Document Open Access Logo

An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons

Author Haitao Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.59.pdf
  • Filesize: 0.9 MB
  • 15 pages

Document Identifiers

Author Details

Haitao Wang
  • Department of Computer Science, Utah State University, Logan, UT, USA

Funding

This research was supported in part by NSF under Grant CCF-2005323.

Cite AsGet BibTex

Haitao Wang. An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.59

Abstract

Given a set S of m point sites in a simple polygon P of n vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for S in P. It is known that the problem has an Ω(n+mlog m) time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in O(n+mlog m) expected time. The previous best deterministic algorithms solve the problem in O(nlog log n+ mlog m) time [Oh, Barba, and Ahn, SoCG 2016] or in O(n+mlog m+mlog² n) time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of O(n+mlog m) time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Algorithm design techniques
Keywords
  • farthest-sites
  • Voronoi diagrams
  • triple-point geodesic center
  • simple polygons

Metrics

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

Related Versions

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. Discrete and Computational Geometry, 56:836-859, 2016. Google Scholar
  2. B. Aronov. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica, 4:109-140, 1989. Google Scholar
  3. B. Aronov, S. Fortune, and G. Wilfong. The furthest-site geodesic Voronoi diagram. Discrete and Computational Geometry, 9:217-255, 1993. Google Scholar
  4. 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
  5. S.W. Bae and K.Y. Chwa. The geodesic farthest-site Voronoi diagram in a polygonal domain with holes. In Proceedings of the 25th ACM Symposium on Computational Geometry (SoCG), pages 198-207, 2009. Google Scholar
  6. S.W. Bae, M. Korman, and Y. Okamoto. The geodesic diameter of polygonal domains. Discrete and Computational Geometry, 50:306-329, 2013. Google Scholar
  7. S.W. Bae, M. Korman, and Y. Okamoto. Computing the geodesic centers of a polygonal domain. Computational Geometry: Theory and Applications, 77:3-9, 2019. Google Scholar
  8. L. Barba. Optimal algorithm for geodesic farthest-point Voronoi diagrams. In Proceedings of the 35th International Symposium on Computational Geometry (SoCG), pages 12:1-12:14, 2019. Google Scholar
  9. B. Chazelle. A theorem on polygon cutting with applications. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 339-349, 1982. Google Scholar
  10. B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1):54-68, 1994. Google Scholar
  11. L.J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. Google Scholar
  12. J. Hershberger. A new data structure for shortest path queries in a simple polygon. Information Processing Letters, 38(5):231-235, 1991. Google Scholar
  13. J. Hershberger and S. Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. Google Scholar
  14. 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
  15. D. Kirkpatrick and J. Snoeyink. Tentative prune-and-search for computing fixed-points with applications to geometric computation. Fundamenta Informaticae, 22(4):353-370, 1995. Google Scholar
  16. C.-H. Liu. A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon. Algorithmica, 82:915-937, 2020. Google Scholar
  17. 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
  18. E. Oh. Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391-409, 2019. Google Scholar
  19. E. Oh and H.-K. Ahn. Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discrete and Computational Geometry, 63:418-454, 2020. Google Scholar
  20. E. Oh, L. Barba, and H.-K. Ahn. The geodesic farthest-point Voronoi diagram in a simple polygon. Algorithmica, 82:1434-1473, 2020. Google Scholar
  21. E. Papadopoulou and D.T. Lee. A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica, 20:319-352, 1998. Google Scholar
  22. 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
  23. F.P. Preparata and M.I. Shamos. Computational Geometry. Springer-Verlag, New York, 1985. Google Scholar
  24. S. Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences, 39:220-235, 1989. Google Scholar
  25. G. Toussaint. Computing geodesic properties inside a simple polygon. Technical report, McGill University, Montreal, Canada, 1989. Google Scholar
  26. H. Wang. On the geodesic centers of polygonal domains. Journal of Computational Geometry, 9:131-190, 2018. 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