On Bregman Voronoi Diagrams

 author = { Frank Nielsen and  Jean-Daniel Boissonnat and Richard Nock },
 title = {On Bregman Voronoi Diagrams},
 booktitle = {ACM-SIAM Symposium on Discrete Algorithms},
 year = {2007},
 isbn = {979-0-898716-24-5},
 pages = {746-755},

Visualizing Bregman Voronoi diagrams on the GPU

Bregman Voronoi diagrams as minimization diagrams.

Voronoi diagrams can be computed as the vertical projection of minimizations diagrams. For example, the ordinary Voronoi diagram is combinatorially equivalent to the lower envelope of unit paraboloids centered at sites. See this animation VorMinDiagram-ParaboloidL2.avi for an illustration. The ordinary minimization diagram can be simplified to an affine diagram: VorMinDiagram-LinearL2.avi (that is computed in practice as the intersection of halfplanes).  
Similarly, for Bregman Voronoi diagrams, we can define first-type affine and second-type curved minimization diagrams:


Affine and curved Voronoi diagrams (Power, Moebius, Anisotropic, Apollonius) and their relationships with power diagrams by means of linearization/manifold intersection and vertical projection have been surveyed in "Curved Voronoi Diagrams" by J.-D. Boissonnat (Springer 2006, Effective comp. geom.). We illustrate interactively these diagrams using a single formula w((x-p)^T Q (x-p))^a-r^a. Here is the video (PowerAndCurvedVoronoiDiagrams.wmv) showing animations of these diagrams.


C++ software (with EPS/PDF output) for computing exactly Bregman Voronoi/Delaunay to come soon...
Last updated January 2007, Frank Nielsen.