LIPIcs.ESA.2020.56.pdf
- Filesize: 2.19 MB
- 15 pages
Document
An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams
Authors
Martin Held 
,
Stefan de Lorenzo
-
Part of:
Volume:
28th Annual European Symposium on Algorithms (ESA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-26
File
Document Identifiers
Author Details
Cite AsGet BibTex
Martin Held and Stefan de Lorenzo. An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.56
https://doi.org/10.4230/LIPIcs.ESA.2020.56
Abstract
We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled & Raichel, Discrete Comput. Geom. 53:547 - 568, 2015] allows to achieve an expected runtime complexity of 𝒪(n log⁴ n), while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest 𝒪(n log² n) as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights, and it yields a truly simple 𝒪(n log n) solution for solving the one-dimensional version of this problem.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Voronoi Diagram
- multiplicative weight
- additive weight
- arc expansion
- overlay arrangement
- implementation
- experiments
- CGAL
- exact arithmetic
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Franz Aurenhammer. The One-Dimensional Weighted Voronoi Diagram. Information Processing Letters, 22(3):119-123, 1986. URL: https://doi.org/10.1016/0020-0190(86)90055-4.
- Franz Aurenhammer and Herbert Edelsbrunner. An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane. Pattern Recognition, 17(2):251-257, 1984. URL: https://doi.org/10.1016/0031-3203(84)90064-5.
- Rudi Bonfiglioli, Wouter van Toll, and Roland Geraerts. GPGPU-Accelerated Construction of High-Resolution Generalized Voronoi Diagrams and Navigation Meshes. In Proceedings of the Seventh International Conference on Motion in Games, pages 26-30, 2014. URL: https://doi.org/10.1145/2668084.2668093.
- Barry N. Boots. Weighting Thiessen Polygons. Economic Geography, 56(3):248-259, 1980. URL: https://doi.org/10.2307/142716.
-
Günther Eder, Martin Held, Steinþór Jasonarson, Philipp Mayer, and Peter Palfrader. On Generating Polygons: Introducing the Salzburg Database. In Proceedings of the 36th European Workshop on Computational Geometry, pages 75:1-75:7, March 2020.
- Computational Geometry and Applications Lab Salzburg. Salzburg Database of Geometric Inputs. https://sbgdb.cs.sbg.ac.at/, 2020.
-
Leonidas Guibas. Kinetic Data Structures. In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, pages 23.1-23.18. Chapman and Hall/CRC, 2001. ISBN 9781584884354.
- Sariel Har-Peled and Benjamin Raichel. On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams. Discrete & Computational Geometry, 53(3):547-568, 2015. URL: https://doi.org/10.1007/s00454-015-9675-0.
- Martin Held and Stefan de Lorenzo. An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams, 2020. URL: http://arxiv.org/abs/2006.14298.
- Kenneth E. Hoff III, John Keyser, Ming Lin, Dinesh Manocha, and Tim Culver. Fast Computation of Generalized Voronoi Diagrams using Graphics Hardware. In Proceedings of the the 26th Annual International Conference on Computer Graphics and Interactive Techniques, pages 277-286. ACM Press/Addison-Wesley Publishing Co., 1999. URL: https://doi.org/10.1145/311535.311567.
- Haim Kaplan, Edgar Ramos, and Micha Sharir. The Overlay of Minimization Diagrams in a Randomized Incremental Construction. Discrete & Computational Geometry, 45(3):371-382, 2011. URL: https://doi.org/10.1007/s00454-010-9324-6.
- The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 5.0 edition, 2019. URL: https://doc.cgal.org/5.0/Manual/packages.html.
- Kira Vyatkina and Gill Barequet. On Multiplicatively Weighted Voronoi Diagrams for Lines in the Plane. Transactions on Computational Science, 13:44-71, 2011. URL: https://doi.org/10.1007/978-3-642-22619-9_3.