Power diagrams: properties, algorithms, and applications
of a point
with respect to a sphere
is given by
denotes the Euclidean
distance function, and
are the center and the radius of
power diagram of a finite set
of spheres in
is a cell complex that
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
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].