reference algorithm for weighted voronoi diagrams?

12
votes

Can someone point me to a reference implementation on how to construct a (multiplicatively and/or additively) weighted voronoi diagram, which is preferably based on Fortune's voronoi algorithm?

My goal: Given a set of points(each point has a weight) and a set of boundary edges(usually a rectangle) I want to construct a weighted voronoi diagram using either python or the processing.org-framework. Here is an example.

What I have worked on so far: So far I have implemented Fortune's algorithm as well as the "centroidal voronoi tessellation" presented in Michael Balzer's paper. Algorithm 3 states how the weights need to be adjusted, however, when I implement this my geometry does not work anymore. To fix this the sweep-line algorithm has to be updated to take weights into account, but I have been unable to do this so far. Hence I would like to see how other people solved this problem.

4
algorithmdata-structuresgeometryvoronoi

4 Answers

10
votes

For additively weighted Voronoi Diagram: Remember that a power diagram in dimension n is only a(n unweighted) Voronoi diagram in dimension n+1.

For that, just recall that the Voronoi diagram of a point set is invariant if you add any constant to the coordinates, and that the weighted Voronoi diagram can thus be written as a non weighted Voronoi diagram using the coordinates, for example in 2D lifted to 3D:
(x_i, y_i, sqrt(C - w_i))
where w_i is the weight of the seed, and C is any arbitrarily large constant (in practice, one just small enough such that C-w_i is positive).
Once your diagram is computed, just discard the last component.

So, basically, you only need to find a library that is able to handle Voronoi diagrams in dimension n+1 compared to your problem. CGAL can do that. This also makes the implementation extremely easy.

4
votes

This computation is not easy, but it is available in CGAL. See the manual pages here.

From CGAL manual
Effective Computational Geometry
Monique
2
votes

There is little `off-the-shelf' open source code out there, for the case where distances to the centers are weighted with a multiplicative factor. To my knowledge, none of the current CGAL packages covers this case.

Takashi Ohyama's beautifully colorful website provides java implementations http://www.nirarebakun.com/voro/emwvoro.html for up to 100 points with a SIMPLE algorithm (Euclidean and Manhattan distances). There is also a paper describing this simple intersection algorithm and an approximate implementation within O(n^3) time, as a plugin to TerraView. However, I cannot find the source of this plugin in the TerraView / TerraLib repository: http://www.geoinfo.info/geoinfo2011/papers/mauricio1.pdf

Aurenhammer and Edelsbrunner describe an optimal n^2 time algorithm, but I'm unaware of available code of that.

0
votes

If you are comfortable digging into Octave, you could reference the code provided in their library.