LIPIcs.SoCG.2016.56.pdf
- Filesize: 0.59 MB
- 15 pages
Document
The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon
Authors
-
Part of:
Volume:
32nd International Symposium on Computational Geometry (SoCG 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-10
Cite As Get BibTex
Eunjin Oh, Luis Barba, and Hee-Kap Ahn. The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.56
Abstract
Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon.
Subject Classification
Keywords
- Geodesic distance
- simple polygons
- farthest-point Voronoi diagram
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Alok Aggarwal, Leonidas J Guibas, James Saxe, and Peter W Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete &Computational Geometry, 4(6):591-604, 1989.
-
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 Proceedings of the 31st Symposium on Compututaional Geometry, SoCG, pages 209-223, 2015.
-
Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic Voronoi diagram. Discrete &Computational Geometry, 9(3):217-255, 1993.
-
T. Asano and G.T. Toussaint. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, 1985.
-
Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. Forest-like abstract Voronoi diagrams in linear time. In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG, pages 133-141, 2014.
-
B Chazelle. A theorem on polygon cutting with applications. In Proceedings 23rd Annual Symposium on Foundations of Computer Science, FOCS, pages 339-349, 1982.
-
Herbert Edelsbrunner and Ernst Peter Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 9(1):66-104, 1990.
-
John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997.
-
Rolf Klein and Andrzej Lingas. Hamiltonian abstract Voronoi diagrams in linear time. In Proceedings of the 5th International Symposium on Algorithms and Computation ISAAC, pages 11-19, 1994.
-
J. S. B. Mitchell. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, pages 633-701. Elsevier, 2000.
-
Evanthia Papadopoulou. k-pairs non-crossing shortest paths in a simple polygon. International Journal of Computational Geometry and Applications, 9(6):533-552, 1999.
-
Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete &Computational Geometry, 4(6):611-626, 1989.
-
Subhash Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences, 39(2):220-235, 1989.