Document Open Access Logo

Piecewise-Linear Farthest-Site Voronoi Diagrams

Authors Franz Aurenhammer , Evanthia Papadopoulou , Martin Suderland

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.30.pdf
  • Filesize: 0.75 MB
  • 11 pages

Document Identifiers

Author Details

Franz Aurenhammer
  • Institute for Theoretical Computer Science, TU Graz, Austria
Evanthia Papadopoulou
  • Faculty of Informatics, Università della Svizzera italiana, Lugano, Switzerland
Martin Suderland
  • Faculty of Informatics, Università della Svizzera italiana, Lugano, Switzerland

Funding

The first author was supported by Projects I 1836-N15 and I 5270-N, Austria Science Fund (FWF). The last two authors were supported in part by Projects 200021E_154387 and 200021E_201356, Swiss National Science Foundation (SNF).

Cite AsGet BibTex

Franz Aurenhammer, Evanthia Papadopoulou, and Martin Suderland. Piecewise-Linear Farthest-Site Voronoi Diagrams. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.30

Abstract

Voronoi diagrams induced by distance functions whose unit balls are convex polyhedra are piecewise-linear structures. Nevertheless, analyzing their combinatorial and algorithmic properties in dimensions three and higher is an intriguing problem. The situation turns easier when the farthest-site variants of such Voronoi diagrams are considered, where each site gets assigned the region of all points in space farthest from (rather than closest to) it. We give asymptotically tight upper and lower worst-case bounds on the combinatorial size of farthest-site Voronoi diagrams for convex polyhedral distance functions in general dimensions, and propose an optimal construction algorithm. Our approach is uniform in the sense that (1) it can be extended from point sites to sites that are convex polyhedra, (2) it covers the case where the distance function is additively and/or multiplicatively weighted, and (3) it allows an anisotropic scenario where each site gets allotted its particular convex distance polytope.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Voronoi diagram
  • farthest-site
  • polyhedral distance
  • polyhedral sites
  • general dimensions

Metrics

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

References

  1. Boris Aronov. A lower bound on Voronoi diagram complexity. Information Processing Letters, 83(4):183-185, 2002. Google Scholar
  2. Franz Aurenhammer. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing, 16(1):78-96, 1987. Google Scholar
  3. Franz Aurenhammer, Scot Drysdale, and Hannes Krasser. Farthest line segment Voronoi diagrams. Information Processing Letters, 100(6):220-225, 2006. Google Scholar
  4. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. Voronoi diagrams and Delaunay Triangulations. World Scientific Publishing Company, 2013. Google Scholar
  5. Gill Barequet, Evanthia Papadopoulou, and Martin Suderland. Unbounded regions of high-order Voronoi diagrams of lines and segments in higher dimensions. In 30th International Symposium on Algorithms and Computation, volume 149 of LIPIcs, pages 62:1-62:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  6. Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete & Computational Geometry, 19(4):485-519, 1998. Google Scholar
  7. Bernard Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry, 10:377-409, 1993. Google Scholar
  8. Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Mira Lee, and Hyeon-Suk Na. Farthest-polygon Voronoi diagrams. Computational Geometry: Theory and Applications, 44(4):234-247, 2011. Google Scholar
  9. L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, and Emo Welzl. Voronoi diagrams of lines in 3-space under polyhedral convex distance functions. Journal of Algorithms, 29(2):238-255, 1998. Google Scholar
  10. Sandip Das and Swami Sarvottamananda. Computing the Minkowski sum of convex polytopes in R^d. CoRR, abs/1811.05812, 2018. URL: http://arxiv.org/abs/1811.05812.
  11. Herbert Edelsbrunner and Raimund Seidel. Voronoi diagrams and arrangements. Discrete & Computational Geometry, 1:25-44, 1986. Google Scholar
  12. Hazel Everett, Daniel Lazard, Sylvain Lazard, and Mohab Safey El Din. The Voronoi diagram of three lines. Discrete & Computational Geometry, 42(1):94-130, 2009. Google Scholar
  13. Christian Icking and Lihong Ma. A tight bound for the complexity of Voroni diagrams under polyhedral convex distance functions in 3D. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pages 316-321, 2001. Google Scholar
  14. Menelaos I. Karavelas, Raimund Seidel, and Eleni Tzanaki. Convex hulls of spheres and convex hulls of disjoint convex polytopes. Computational Geometry: Theory and Applications, 46(6):615-630, 2013. Google Scholar
  15. Victor Klee. On the complexity of d-dimensional Voronoi diagrams. Archiv der Mathematik, 34(1):75-80, 1980. Google Scholar
  16. Vladlen Koltun and Micha Sharir. Polyhedral Voronoi diagrams of polyhedra in three dimensions. Discrete & Computational Geometry, 31(1):83-124, 2004. Google Scholar
  17. Joseph S. B. Mitchell and Joseph O'Rourke. Computational Geometry Column 42. Intern. Journal of Computational Geometry & Applications, 11(5):573-582, 2001. Google Scholar
  18. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd Edition), volume 501. John Wiley & Sons, 2009. Google Scholar
  19. Evanthia Papadopoulou and Sandeep Kumar Dey. On the farthest line-segment Voronoi diagram. Intern. Journal of Computational Geometry & Applications, 23(6):443-460, 2013. Google Scholar
  20. Raimund Seidel. On the number of faces in higher-dimensional Voronoi diagrams. In Proceedings of the Third Annual Symposium on Computational Geometry, pages 181-185, 1987. Google Scholar
  21. Micha Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete & Computational Geometry, 12:327-345, 1994. 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