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.

Answer 1

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:

---

          

Answer 2

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.