License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.56
URN: urn:nbn:de:0030-drops-129224
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12922/
Go to the corresponding LIPIcs Volume Portal

Held, Martin ; de Lorenzo, Stefan

An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams

pdf-format:
LIPIcs-ESA-2020-56.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{held_et_al:LIPIcs:2020:12922,
  author =	{Martin Held and Stefan de Lorenzo},
  title =	{{An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12922},
  URN =		{urn:nbn:de:0030-drops-129224},
  doi =		{10.4230/LIPIcs.ESA.2020.56},
  annote =	{Keywords: Voronoi Diagram, multiplicative weight, additive weight, arc expansion, overlay arrangement, implementation, experiments, CGAL, exact arithmetic}
}

Keywords: Voronoi Diagram, multiplicative weight, additive weight, arc expansion, overlay arrangement, implementation, experiments, CGAL, exact arithmetic
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: The source code of our implementation is available at GitHub and can be used freely under the https://www.gnu.org/licenses/gpl-3.0.html: https://github.com/cgalab/wevo.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI