- paper pdf (SODA)
- Short slide presentation (25') given at SODA'07: short presentation
- Full presentation (45')
- ...will update full journal version soon

@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}, }

- 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.

*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.

- First-type
- 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)

Similarly, for Bregman Voronoi diagrams, we can define first-type affine and second-type curved minimization diagrams:

- First-type affine diagram example for the Kullback-Leiber divergence: VorMinDiagram-LinearKL.avi
- Second-type curved diagram example (dually affine) for the Kullback-Leibler divergence: VorMinDiagram-CurvedKL.avi

- 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.

Last updated January 2007, Frank Nielsen.