Power Diagrams: Properties, Algorithms and Applications

The power pow (x, s) of a point x with respect to a sphere s in Euclidean d-space Eᵈ is given by d² (x, z) - r², where d denotes the Euclidean distance function, and z and r are the center and the radius of s. The power diagram of a finite set S of spheres in Eᵈ is a cell complex that associates each s S with the convex domain \ x Eᵈ | {pow (x, s) < pow (x, t), for all t S - \ s\ \}. The close relationship to convex hulls and arrangements of hyperplanes is investigated and exploited. Efficient algorithms that compute the power diagram and its order-k modifications are obtained. Among the applications of these results are algorithms for detecting k-sets, for union and intersection problems for cones and paraboloids, and for constructing weighted Voronoi diagrams and Voronoi diagrams for spheres. Upper space bounds for these geometric problems are derived.