Abstract
The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is \(\varOmega (n+m\log m)\), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve \(O( (n+m) \log (n+m) )\) and \(O(n+m\log m\log ^2n)\) time, which are optimal for \(m=\varOmega (n)\) and \(m=O(\frac{n}{\log ^3n})\), respectively. In this paper, we give a construction algorithm with \(O( n + m ( \log m+ \log ^2 n ) )\) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in \(O(\log n)\) time, then the construction time will become the optimal \(O(n+m\log m)\). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in \(O(\log n)\) time.
Similar content being viewed by others
References
Aronov, B.: On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica 4(1–4), 109–140 (1989)
Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)
Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485–524 (1991)
Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317–340 (1986)
Guibas, L.J., Hershberger, J.: Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci. 39(2), 126–152 (1989)
Guibas, L.J., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1–4), 209–233 (1987)
Hershberger, J.: A new data structure for shortest path queries in a simple polygon. Inf. Process. Lett. 38(5), 231–235 (1991)
Liu, C.-H.: A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon. In: 34th International Symposium on Computational Geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary, pp. 58:1–58:14 (2018)
Mehlhorn, K., Sanders, P..: Sorted sequences. In: Algorithms and Data Structures: The Basic Toolbox. Springer, Berlin (2008)
Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633–701. Elsevier, Amsterdam (2000)
Oh, E., Ahn, H.-K.: Voronoi diagrams for a moderate-sized point-set in a simple polygon. In: 33rd International Symposium on Computational Geometry, SoCG 2017, July 4–7, 2017, Brisbane, Australia, pp. 52:1–52:15 (2017)
Papadopoulou, E., Lee, D.T.: A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica 20(4), 319–352 (1998)
Tarjan, R.E.: Updating a balanced search tree in O(1) rotations. Inf. Process. Lett. 16(5), 253–257 (1983)
Tarjan, R.E.: Efficient Top-Down Updating of Red–Black Trees. Technical Report TR-006-85. Department of Computer Science, Princeton University (1985)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version appeared in the Proceedings of the 34th International Symposium on Computational Geometry 2018 (SoCG’18) [8].
Rights and permissions
About this article
Cite this article
Liu, CH. A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. Algorithmica 82, 915–937 (2020). https://doi.org/10.1007/s00453-019-00624-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-019-00624-2