Document Open Access Logo

The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon

Authors Eunjin Oh, Luis Barba, Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.56.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Eunjin Oh
Luis Barba
Hee-Kap Ahn

Cite AsGet 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.
Keywords
  • Geodesic distance
  • simple polygons
  • farthest-point Voronoi diagram

Metrics

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

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic Voronoi diagram. Discrete &Computational Geometry, 9(3):217-255, 1993. Google Scholar
  4. T. Asano and G.T. Toussaint. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University, 1985. Google Scholar
  5. 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. Google Scholar
  6. B Chazelle. A theorem on polygon cutting with applications. In Proceedings 23rd Annual Symposium on Foundations of Computer Science, FOCS, pages 339-349, 1982. Google Scholar
  7. 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. Google Scholar
  8. John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. Google Scholar
  9. 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. Google Scholar
  10. J. S. B. Mitchell. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, pages 633-701. Elsevier, 2000. Google Scholar
  11. Evanthia Papadopoulou. k-pairs non-crossing shortest paths in a simple polygon. International Journal of Computational Geometry and Applications, 9(6):533-552, 1999. Google Scholar
  12. Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete &Computational Geometry, 4(6):611-626, 1989. Google Scholar
  13. 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 Imprint Privacy Contact