me | department | university | teaching | research | disclaimer | personal stuff



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.


[Image of multiplicatively-weighted Voronoi diagram] A multiplicatively weighted Voronoi diagram in the Euclidean norm.
[Image of multiplicatively-weighted Voronoi diagram] 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.



[Image of CS Logo]
file last modified: Wednesday, 26-Aug-2020 08:49:33 CEST
email address
Copyright © 2022 Martin Held. All rights reserved.
[Rock climbing]