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^d $ is given by $d^2 (x,z) - r^2 $, 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^d $ is a cell complex that associates each $s \in S$ with the convex domain $\{ x \in E^d | {\operatorname{pow}} (x,s) < {\operatorname{pow}} (x,t), {\text{ for all }} t \in 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.