Power diagrams: properties, algorithms, and applications

F. Aurenhammer

Abstract:

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 \mid pow(x,s) < pow(x,t), \mbox{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.

Reference: F. Aurenhammer. Power diagrams: properties, algorithms, and applications. SIAM Journal on Computing, 16(1):78-96, 1987. [IIG-Report-Series F120, TU Graz, Austria, 1983].