Visualizing bregman voronoi diagrams

ABSTRACT

Voronoi diagrams are fundamental geometric structures that partition the space into elementary regions of influence defining discrete proximity graphs and dually well-shaped Delaunay triangulations [Aurenhammer & Klein, 2000]. In this video, we explain and illustrate a recent generalization of Voronoi diagrams [Nielsen et al., 2007] to a wide class of distortion measures called Bregman divergences [Banerjee et al., 2005].

REFERENCES

• 1: F. Aurenhammer and R. Klein. Voronoi Diagrams. In Handbook of Computational Geometry, pp. 201--290. Elsevier, 2000.
• 2: A. Banerjee, S. Merugu, I.S. Dhillon, and J. Ghosh. Clustering with Bregman divergences. In SIAM Data Mining, pp. 234--245, 2004.
• 3: F. Nielsen, J.-D. Boissonnat, and R. Nock. On Bregman Voronoi diagrams. In ACM-SIAM Symposium on Discrete Algorithms, pp. 746--755, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory

Keywords:
Bregman divergences, Voronoi diagrams, computational information geometry