Bregman Voronoi Diagrams: Properties, Algorithms and Applications

Abstract

The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define many variants of Voronoi diagrams depending on the class of objects, the distance functions and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g. k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connexion with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation. Finally, we give some applications of Bregman Voronoi diagrams which are of interest in the context of computational geometry and machine learning.

Extend the proceedings abstract of SODA 2007 (46 pages, 15 figures)

References in corpus (2)

• Statistical exponential families: A digest with flash cards
• Hyperbolic Voronoi diagrams made easy

Cited by in corpus (29)

• Extropy: Complementary Dual of Entropy
• On a generalization of the Jensen-Shannon divergence and the JS-symmetrization of distances relying on abstract means
• An elementary introduction to information geometry
• The Burbea-Rao and Bhattacharyya centroids
• Re-examination of Bregman functions and new properties of their divergences
• Chernoff information of exponential families
• Guaranteed bounds on the Kullback-Leibler divergence of univariate mixtures using piecewise log-sum-exp inequalities
• Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
• Joint Color-Spatial-Directional clustering and Region Merging (JCSD-RM) for unsupervised RGB-D image segmentation
• $k$-MLE: A fast algorithm for learning statistical mixture models
• On the Kullback-Leibler divergence between discrete normal distributions
• Revisiting Chernoff Information with Likelihood Ratio Exponential Families
• Monte Carlo Information Geometry: The dually flat case
• Hilbert geometry of the Siegel disk: The Siegel-Klein disk model
• On $f$-divergences between Cauchy distributions
• The hyperbolic Voronoi diagram in arbitrary dimension
• Cumulant-free closed-form formulas for some common (dis)similarities between densities of an exponential family
• Information measures and geometry of the hyperbolic exponential families of Poincaré and hyperboloid distributions
• On the Kullback-Leibler divergence between location-scale densities
• A scaled Bregman theorem with applications
• Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality
• Evolving a Vector Space with any Generating Set
• Power to the Points: Validating Data Memberships in Clusterings
• On Voronoi diagrams and dual Delaunay complexes on the information-geometric Cauchy manifolds
• Hyperlink Regression via Bregman Divergence
• A directed isoperimetric inequality with application to Bregman near neighbor lower bounds
• Information Geometry and Asymptotic Theory for SMML Estimators
• On the Embeddability of Delaunay Triangulations in Anisotropic, Normed, and Bregman Spaces
• On the existence of a neutral region