On the generality of power diagrams

F. Aurenhammer

Abstract:

A set $s = \{ x \mid <x-z>^2 = r^2 \}$ in Euclidean space is called a sphere with center $z$ and positive radius $r$. For an arbitrary point $x$, $<x-z>^2 = r^2$ is the power of $x$ with respect to $s$. Extending these concepts to imaginary radii, they are exploited to show the equivalence of two types of cell complexes: those that can be obtained by projection of convex polyhedra, and those that come from projecting levels in arrangement of hyperplanes. As a consequence, higher-order Voronoi diagrams can be constructed by determining a convex hull.

Reference: F. Aurenhammer. On the generality of power diagrams. IIG Report F126, TU Graz, Austria, 1983.