An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane
Marina L. Gavrilova, Jon George Rokne · International Journal of Computer Mathematics · 1996
An algorithm for transforming a Voronoi diagram for point sites to a Voronoi diagram for weighted sites (power diagram) is presented. The algorithm was implemented and experiments suggest that the average running time of the algorithm and the space required are 0(N) in the plane. The worst case complexity can be shown to be bounded by 0(N2) although it is conjectured that it is O(N).