# Power diagrams: properties, algorithms, and applications

F. Aurenhammer

### Abstract:

The power of a point with respect to a sphere in Euclidean -space is given by , where denotes the Euclidean distance function, and and are the center and the radius of . The power diagram of a finite set of spheres in is a cell complex that associates each with the convex domain . The close relationship to convex hulls and arrangements of hyperplanes is investigated and exploited. Efficient algorithms that compute the power diagram and its order- modifications are obtained. Among the applications of these results are algorithms for detecting -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].