Document Open Access Logo

Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams

Author Luis Barba

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.12.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Luis Barba
  • Department of Computer Science, ETH Zürich, Switzerland

Cite As Get BibTex

Luis Barba. Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.12

Abstract

Let P be a simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. Given a set S of m sites being a subset of the vertices of P, we present the first randomized algorithm to compute the geodesic farthest-point Voronoi diagram of S in P running in expected O(n + m) time. That is, a partition of P 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 distance. This algorithm can be extended to run in expected O(n + m log m) time when S is an arbitrary set of m sites contained in P.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
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

Related Versions

References

  1. Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou Carufel, Matias Korman, and Eunjin Oh. A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon. Discrete &Computational Geometry, 56(4):836-859, December 2016. URL: http://dx.doi.org/10.1007/s00454-016-9796-0.
  2. Boris Aronov. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica, 4(1-4):109-140, 1989. Google Scholar
  3. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic Voronoi diagram. Discrete &Computational Geometry, 9(1):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. Luis Barba. Geodesic farthest-point Voronoi diagram in linear time. CoRR, abs/1809.01481, 2018. URL: http://arxiv.org/abs/1809.01481.
  6. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proceedings of the twenty-sixth annual ACM-SIAM Symposium on Discrete Algorithms, pages 1655-1670. SIAM, 2014. Google Scholar
  7. Bernard Chazelle. A theorem on polygon cutting with applications. In Proceedings of FOCS, pages 339-349, 1982. URL: http://dx.doi.org/10.1109/SFCS.1982.58.
  8. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete &Computational Geometry, 6(1):485-524, 1991. Google Scholar
  9. Mark De Berg, Marc Van Kreveld, Mark Overmars, and Otfried Cheong Schwarzkopf. Computational geometry. In Computational geometry, pages 1-17. Springer, 2000. Google Scholar
  10. 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
  11. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209-233, 1987. Google Scholar
  12. John Hershberger and Subhash Suri. Matrix Searching with the Shortest-Path Metric. SIAM Journal on Computing, 26(6):1612-1634, 1997. Google Scholar
  13. Chih-Hung Liu. A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. In LIPIcs-Leibniz International Proceedings in Informatics, volume 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  14. J. S. B. Mitchell. Geometric Shortest Paths and Network Optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633-701. Elsevier, 2000. Google Scholar
  15. Eunjin Oh. Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams. In To appear in the Proceedings of the 31st annual ACM-SIAM Symposium on Discrete Algorithms, page TBD, 2019. Google Scholar
  16. Eunjin Oh and Hee-Kap Ahn. Voronoi diagrams for a moderate-sized point-set in a simple polygon. In LIPIcs-Leibniz International Proceedings in Informatics, volume 77. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  17. Eunjin Oh, Sang Won Bae, and Hee-Kap Ahn. Computing a geodesic two-center of points in a simple polygon. In Latin American Symposium on Theoretical Informatics, pages 646-658. Springer, 2016. Google Scholar
  18. Eunjin Oh, Luis Barba, and Hee-Kap Ahn. The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon. In LIPIcs-Leibniz International Proceedings in Informatics, volume 51. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  19. 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
  20. Richard Pollack, Micha Sharir, and Günter Rote. Computing the geodesic center of a simple polygon. Discrete &Computational Geometry, 4(1):611-626, 1989. Google Scholar
  21. 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 About DROPS Imprint Privacy Contact