**F. Aurenhammer**

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.