Multiplicatively Weighted Voronoi Diagrams

In 1984, Aurenhammer and Edelsbrunner introduced an O(N^2) time algorithm to compute the multiplicatively weighted Voronoi diagram of N weighted point sites in the standard Euclidean metric. We pick up the lead and investigate multiplicatively weighted Voronoi diagrams in the Euclidean and in the maximum norm.

Joint work with Günther Eder and Stefan de Lorenzo.

This work was supported by Austrian Science Fund (FWF): Grants ORD 53-VO and P31013-N31.

				A multiplicatively weighted Voronoi diagram in the Euclidean norm.
				A multiplicatively weighted Voronoi diagram in the maximum norm.

Related publications:

M. Held, S. de Lorenzo (2020):
"An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams".
Proc. ESA 2020, pp. 56:1-56:15, Pisa, Italy, Sep 2020.

M. Held, S. de Lorenzo (2020):
"On Implementing Multiplicatively Weighted Voronoi Diagrams".
Proc. 36th EuroCG, pp. 15:1-15:9, Würzburg, Germany, March 2020.

G. Eder, M. Held (2019):
"Weighted Voronoi Diagrams in the Maximum Norm".
Int. J. Comput. Geom. Appl. 29(3):239-250, 2019.

file last modified: Wednesday, 26-Aug-2020 08:49:33 CEST
held@cs.sbg.ac.at