On Bregman Voronoi Diagrams
@InProceedings{NBN-BregmanVoronoi-2007,
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
VIDEO (2 MB AVI) Bregman divergences
are a powerful parameterized family of distance measures that may not be
symmetric. Contrary to the Euclidean plane, the space is not homogeneous nor
isotropic (that is both the origin and direction of a coordinate system are
important). In this interactive shader, we present the various shapes of
Bregman disks. Because Bregman divergences are not necessarily symmetric, we
can define three types of balls;
- First-type ball(c,r)={x | D(c,x)<=r} RED,
- Second-type BLUE, ball'(c,r)={x | D(x,c)<=r}, and
- Third-type symmetrized Ball(c,r)={x | D(c,x)+D(x,c)<=2r}
GREEN.
There is also a similar shader to define the Bregman circles
VIDEO
(3.5 MB AVI; PS we used some trick to make the border of Bregman disks one
pixel width) Using this shader, we can `check' that first-type disks may
not always be convex but second-type disks are always convex.
VIDEO (2 MB AVI). Bregman Voronoi
diagrams unifies in the same framework both the ordinary Euclidean Voronoi
diagram and statistical Voronoi diagrams (used in computer vision, speech
recognition, etc.) [SODA'07]. This video shows the interactive rasterization
of Bregman Voronoi diagrams on GPU. Because divergences are not symmetric
measures, we can define three types of Voronoi diagrams related by dualities;
here first-type linear (RED), second-type curved (BLUE), and third-type
symmetrized (GREEN) diagrams. For metrics, they all collapse to the same
(ordinary) diagram (RED).
VIDEO (4.5 MB AVI). This GPU demo
consists of two shaders running simultaneously showing the three primal
Voronoi diagrams and the corresponding three dual Voronoi diagrams. (This
comes from the fact that any Bregman divergence admits a dual Bregman
divergence.) The first-type linear bisector in the primal Voronoi diagram
(RED, here, exponential loss measure) maps to a dual curved bisector in the
dual Bregman Voronoi diagram (here, the dual measure is the unnormalized
Shannon entropy). Similarly, the second-type curved bisector in the primal
diagram maps to a linear bisector in the dual diagram (BLUE). Symmetrized
divergence bisectors are shown in GREEN.
VIDEO (2 MB AVI). This video provides a
real-time session recording of our 3D GPU volume renderer of Bregman balls for
various Bregman divergences enclosing a given data set. The Itakura-Saito 3D
ball (mainly used in sound processing) is particularly interesting since it is
non-convex. This application let us visualize a provably-small enclosing ball
of a set of points as computed by the algorithm described in [SoCG'06].
- First-
(blue), second-(green) and symmetrized (red) Voronoi diagrams for the relative
entropy divergence:
- Ordinary
affine Voronoi diagram
- Second-type
curved (but dually affine) Kullback-Leibler diagram (Relative entropy)
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:
BACKGROUND
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.
REFERENCES
- F. Nielsen and R. Nock, "On Approximating the Smallest Enclosing Bregman
Balls" ACM Symposium on Computational Geometry (SoCG), pp. 485-486, 2006.
- F. Nielsen, J.-D. Boissonnat and R. Nock, "On Bregman Voronoi Diagrams",
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
C++ software
(with EPS/PDF output) for computing exactly Bregman Voronoi/Delaunay to come
soon...
Last updated January 2007, Frank Nielsen.