Power diagram

In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from a set of circles.

In this interpretation, the set of circle centers in the cross-section plane are the perpendicular projections of the three-dimensional Voronoi sites, and the squared radius of each circle is a constant K minus the squared distance of the corresponding site from the cross-section plane, where K is chosen large enough to make all these radii positive.

[2][3] More generally, because of the equivalence with higher-dimensional halfspace intersections, d-dimensional power diagrams (for d > 2) may be constructed by an algorithm that runs in time

[6] Other applications of power diagrams include data structures for testing whether a point belongs to a union of disks,[2] algorithms for constructing the boundary of a union of disks,[2] and algorithms for finding the closest two balls in a set of balls.

[7] It is also used for solving the semi-discrete optimal transportation problem[8] which in turn has numerous applications, such as early universe reconstruction[9] or fluid dynamics.

[10] Aurenhammer (1987) traces the definition of the power distance to the work of 19th-century mathematicians Edmond Laguerre and Georgy Voronoy.

[3] Fejes Tóth (1977) defined power diagrams and used them to show that the boundary of a union of n circular disks can always be illuminated from at most 2n point light sources.