reference algorithm for weighted voronoi diagrams?

Question

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.

Auer

Answer 1

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.

Squeaky

Answer 2

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

---

---

See also the Effective Computational Geometry project, which employs and supports CGAL:

---

          

Obtect

Answer 3

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.

Saddler

Answer 4

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

Catabolite

Also, the library often provides external resources for specific algorithms or implementations that may be helpful. – Catabolite

Thanks for your response! I have looked at the the Octave documentation, but unfortunately I did not see any API's describing how I can construct weighted voronois. It seems to only support general voronoi diagrams for e.g. nearest neighbor analysis. Did I miss something? – Auer