Source-linked AI summary
Bregman Voronoi Diagrams: Properties, Algorithms and Applications
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock
TL;DR
Ordinary Voronoi diagrams do not directly fit statistical spaces whose divergences may be asymmetric and violate metric axioms. The paper builds a Bregman-divergence framework with multiple diagram types, lifting-based computation, extensions, triangulations, and applications. It concludes that these diagrams retain surprisingly similar combinatorial and geometric properties to Euclidean analogs, while their complexity can grow exponentially with dimension.
Problem
Statistical and machine-learning spaces often require nonsymmetric divergences rather than metrics, while statistical Voronoi diagrams had received very limited prior study.
Method
The paper defines several Bregman Voronoi diagrams, relates them through Legendre duality, computes them by lifting points into an extra dimension, and develops weighted variants and Bregman triangulations.
Results
Bregman Voronoi diagrams and their triangulations share surprisingly similar combinatorial and geometric properties with Euclidean Voronoi and Delaunay structures.
Takeaways & Limitations
The framework supports applications involving entropic divergences in information retrieval, data mining, knowledge discovery, image processing, computational geometry, and machine learning.
Takeaways & Limitations
Combinatorial complexity depends exponentially on dimension, making efficient high-dimensional data structures an open research need.
Abstract
from arXiv · showhide
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.
1 Introduction and prior work
The paper develops Bregman Voronoi diagrams to extend ordinary Euclidean diagrams to asymmetric divergences and statistical spaces. It establishes diagram correspondences, efficient constructions, related triangulations, and applications in computational geometry and machine learning.
- Foundations: Voronoi diagrams partition Euclidean space into cells whose points are closer to one site than to any other under a distance function.The sites are also called Voronoi generators.
- Motivation: Machine-learning data often lie in nonmetric spaces, requiring asymmetric pseudo-distances or divergences instead of ordinary metrics.Examples include statistical parameter spaces where vectors represent distributions.
- Motivation: Statistical Voronoi diagrams had received limited prior study, motivating a broader treatment based on Bregman divergences.The paper positions its framework as generalizing and subsuming preliminary studies using Kullback-Leibler and related divergences.
- Contributions: Because Bregman divergences are asymmetric, the paper defines affine, curved, and symmetrized diagram types linked through the Legendre transformation.The affine cells are convex polyhedra, while the corresponding curved diagram has curved cells.
- Contributions: A higher-dimensional lifting computes Bregman Voronoi diagrams and yields combinatorial bounds; weighted, k-order, and k-bag variants are also introduced.The weighted class is identified with affine or power diagrams.
- Contributions: The paper defines two Bregman triangulations, including a geodesic version dual to the first-type Bregman Voronoi diagram, and gives applications in geometry and machine learning.The first triangulation captures important properties of Delaunay triangulation.
2 Bregman divergences
Bregman divergences generalize squared Euclidean and several information-theoretic divergences through strictly convex differentiable generator functions. Their geometry, duality, symmetry conditions, and statistical interpretation support Voronoi constructions and related applications.
- Definition and geometry: A Bregman divergence is generated by a strictly convex differentiable function and measures the discrepancy between two points through that generator.The divergence is geometrically the vertical gap between the graph of the generator and the tangent hyperplane at the second point.
- Basic properties: Bregman divergences are generally asymmetric; symmetry holds if and only if the generator’s Hessian is constant on the domain.Constant Hessians yield generalized quadratic distances.
- Basic properties: Bregman divergences are nonnegative, convex in their first argument, and not necessarily convex in their second argument.The divergence equals zero exactly when the two points coincide.
- Examples and construction: The framework includes squared Euclidean, generalized quadratic, Mahalanobis, Kullback-Leibler, and Itakura-Saito divergences.Positive linear combinations of generators also produce divergences suitable for heterogeneous data sets.
- Legendre duality: Legendre duality maps a Bregman divergence to a dual divergence through DF(p||q) = DF*(q′||p′), with dual coordinates defined by gradients.The convex conjugate satisfies ∇F* = ∇^-1F and (F*)* = F.
- Statistical interpretation: For exponential-family distributions, Kullback-Leibler divergence is a Bregman divergence in natural parameters and equals the dual divergence in expectation parameters.Specifically, KL(θp||θq) = DF(θq||θp) and DF(θp||θq) = DF*(μq||μp).
3 Elements of Bregman geometry
Bregman geometry distinguishes asymmetric bisectors and balls through primal and dual representations, linked by Legendre transformation and a lifting map. These constructions support geometric complexity bounds, projections, orthogonality, and geodesics.
- Bregman bisectors: Asymmetry yields distinct first- and second-type bisectors: the first is linear in primal space, while the second is potentially curved but linear in gradient space.They coincide for symmetric divergences and correspond through the Legendre transformation.
- Bregman bisectors: The first-type bisector is a hyperplane whose defining values place p and q on opposite sides.Its evaluations at p and q are determined by the directed divergences and have opposite signs.
- Bregman spheres and lifting: First-type Bregman balls are convex, whereas second-type balls need not be convex, as illustrated for the Itakura-Saito divergence.The associated bounding spheres are obtained by replacing the ball inequalities with equalities.
- Bregman spheres and lifting: Lifting x to (x, F(x)) converts Bregman spheres into intersections of the convex hypersurface F with hyperplanes, with the inverse mapping recovering center and radius.A hyperplane z = ⟨x, a⟩ + b maps to center c = ∇^-1F(a) and radius ⟨a, c⟩ − F(c) + b.
- Projection, orthogonality and geodesics: Bregman projections are unique, and the induced geodesic ΓF(p, q) is unique, minimizes the relevant path length, and is Bregman-orthogonal to the first-type bisector.The dual straight path Λ(p, q) is orthogonal to the corresponding dual bisector, while exponential-family paths minimize information length.
4 Bregman Voronoi diagrams
Bregman Voronoi diagrams generalize Euclidean Voronoi diagrams through minimization diagrams of asymmetric divergences, yielding affine, curved, and symmetrized variants. Legendre, polytope, and power-diagram correspondences support efficient construction, complexity bounds, and higher-order extensions.
- Definitions: Bregman Voronoi diagrams are minimization diagrams of Bregman divergences, extending the Euclidean Voronoi construction.The Euclidean diagram is recovered when D_i(x) = ||x − p_i||^2.
- Three diagram types: Because Bregman divergences are asymmetric, the paper defines first-type affine, second-type curved, and third-type symmetrized diagrams.First-type cells are convex polyhedra because their bisectors are hyperplanes; second-type diagrams generally have curved faces.
- Legendre correspondence: The first- and second-type diagrams correspond through Legendre duality, and the curved second-type diagram can be constructed in gradient space before mapping cells back.Construction reduces to an affine diagram in X′ followed by ∇F^-1.
- Symmetrization: The symmetrized diagram is obtained by computing an affine diagram in R^2d, intersecting it with a d-dimensional manifold, and projecting to X.This gives a three-step reduction from the symmetrized construction to an affine diagram.
- Algorithms and extensions: Type-1 and type-2 diagrams have complexity Θ(n⌊(d+1)/2⌋) and optimal construction time Θ(n log n + n⌊(d+1)/2⌋), while symmetrized diagrams have O(nd) complexity and time.The paper also characterizes k-order diagrams as weighted Bregman diagrams and gives k-bag complexity O(n⌊(k+d)/2⌋).
- Power-diagram correspondence: Type-1 Bregman diagrams correspond to power diagrams, although not every power diagram is a Bregman diagram because every Bregman site has a nonempty cell.Scaling the divergence preserves the affine Bregman diagram but changes the corresponding power-diagram centers and radii.
5 Bregman triangulations
The paper develops two Bregman triangulations: a straight-edged Bregman Delaunay triangulation derived by lifting, and a curved geodesic triangulation dual to the first-type Bregman Voronoi diagram.
- 5.1 Bregman Delaunay triangulations: The Bregman Delaunay triangulation is obtained by vertically projecting the lower convex hull of lifted sites.Its vertices are the original sites and it covers their Euclidean convex hull.
- 5.1 Bregman Delaunay triangulations: Each simplex in the Bregman Delaunay triangulation has an empty circumscribing Bregman sphere, uniquely characterizing the triangulation in general position.Equivalently, simplices correspond to subsets admitting an empty Bregman sphere through their sites.
- 5.1 Bregman Delaunay triangulations: A local regularity condition on every pair of adjacent facets characterizes the Bregman triangulation.The condition compares each opposite vertex with the open Bregman ball circumscribing the neighboring facet.
- 5.1 Bregman Delaunay triangulations: The Bregman Delaunay triangulation satisfies the minimax optimality criterion minimizing the largest Bregman radius among all triangulations.The criterion is stated as delF(S) = minT∈T(S) maxτ∈T r(τ).
- 5.2 Bregman geodesic triangulations: The geodesic Bregman triangulation is obtained by mapping a dual regular triangulation through the inverse gradient, producing curved edges between sites.It is the geometric dual of the first-type Bregman Voronoi diagram.
- 5.2 Bregman geodesic triangulations: For symmetric divergences, the two Bregman triangulations are combinatorially equivalent and dual to the Bregman Voronoi diagram; they coincide for squared Euclidean distance.For general Bregman divergences, they are distinct.
6 Applications
The applications develop Bregman centroids and Lloyd quantization, ε-sampling, point-location structures, and learning-theoretic uses based on Bregman balls and Voronoi diagrams.
- 6.1 Centroidal Bregman Voronoi diagrams and Lloyd quantization: The Bregman centroid of a density coincides with its mass centroid and is independent of the chosen Bregman divergence.The centroid is uniquely defined under the stated setup.
- 6.1 Centroidal Bregman Voronoi diagrams and Lloyd quantization: Lloyd’s algorithm alternates Bregman Voronoi construction with moving sites to their cell centroids, converging to a local minimizer.The procedure computes centroidal Bregman Voronoi diagrams for k points.
- 6.2 ε-nets: An ε-sample controls the maximum Bregman divergence from domain points to their nearest sample, while an ε-net additionally enforces pairwise separation.The ε-net condition requires one directed divergence between every pair to exceed ε.
- 6.2 ε-nets: The greedy ε-net algorithm repeatedly inserts the domain vertex farthest from the current sample set until the ε-sample and separation conditions hold.The finite search uses vertices of the restricted Bregman Voronoi diagram.
- 6.2 ε-nets: For C2 generator functions, Bregman balls on compact domains are fat, enabling efficient point-location data structures and related geometric applications.Fatness means each Bregman ball can be covered by a constant number of convex Euclidean balls.
- 6.3 VC-dimension, classification and learning: The class of all Bregman balls in Rd has VC dimension d + 1, supporting extensions of geometric covering results and applications to classification and k-nearest neighbors.The paper connects these results to Bregman-ball covers, k-order Voronoi diagrams, and proximity choices in k-NN.
7 Conclusion
Bregman Voronoi diagrams extend ordinary Voronoi diagrams while preserving surprisingly similar combinatorial and geometric properties. Their exponential dimension dependence makes efficient data structures an important direction for future research.
- Bregman Voronoi diagrams are a natural extension of ordinary Voronoi diagrams.
- They share surprisingly similar combinatorial and geometric properties with Euclidean Voronoi diagrams.
- Their entropic-divergence variants are expected to support applications in information-theoretic settings.
- Their combinatorial complexity depends exponentially on dimension, limiting scalability in high-dimensional applications.
- Efficient data structures for high-dimensional Bregman Voronoi diagrams remain a major avenue for further research.