Introduction
The Voronoi diagram is a fundamental structure in computational geometry, traditionally used to partition space into regions based on proximity to a set of sites using Euclidean distance. However, many modern applications in machine learning, signal processing, and information theory operate in spaces where Euclidean distance is inappropriate. For instance, when comparing probability distributions, the Kullback-Leibler (KL) divergence is the standard measure, yet it lacks the symmetry and triangle inequality required of a true metric.
This paper provides a unified geometric framework for constructing Voronoi diagrams and Delaunay triangulations using Bregman divergences. By bridging the gap between computational geometry and information geometry, the authors demonstrate that these non-metric diagrams can be computed as efficiently as their Euclidean counterparts.
Defining Bregman Divergences
Bregman divergences are a broad class of distance-like functions defined by a strictly convex generator function $F$. For any two points $p$ and $q$, the divergence $D_F(p||q)$ represents the difference between the value of $F$ at $p$ and the value of the first-order Taylor expansion of $F$ around $q$ evaluated at $p$.
Geometrically, as shown in the figure above, the divergence is the vertical distance between the point $\hat{p}$ on the convex surface and the tangent hyperplane $H_q$ at $\hat{q}$. This definition encompasses many familiar measures, including squared Euclidean distance (where $F(x) = x^2$), KL-divergence, and the Itakura-Saito distance.
Algorithmic Framework and Duality
A central challenge of Bregman Voronoi diagrams is that they are generally non-symmetric ($D_F(p||q) \neq D_F(q||p)$). This leads to two distinct types of diagrams:
- First-type diagrams: Based on $D_F(x||p_i)$, which result in cells with flat, polyhedral faces.
- Second-type diagrams: Based on $D_F(p_i||x)$, which result in curved faces in the primal space but become flat in the dual gradient space.
The authors introduce several key technical breakthroughs to handle these structures:
- The Lifting Map: They prove that a $d$-dimensional Bregman Voronoi diagram is the vertical projection of a $(d+1)$-dimensional convex polytope. This transformation linearizes the non-linear proximity problem.
- Power Diagram Equivalence: Perhaps the most significant algorithmic result is the proof that any first-type Bregman Voronoi diagram is equivalent to a power diagram (a weighted Voronoi diagram). This allows researchers to use existing, highly optimized linear-time algorithms to compute complex statistical diagrams.
- Legendre Duality: By utilizing the Legendre transform, the authors establish a dual relationship between points and gradients, allowing for the seamless conversion between the two types of diagrams.
Applications to Statistical Families
The theory applies directly to any statistical model within the exponential family. By mapping distributions like Bernoulli, Poisson, Normal, or Dirichlet to their corresponding Bregman generator functions, one can perform geometric operations directly on the space of parameters.
As illustrated in the table above, different choices of $F$ allow the framework to adapt to the specific noise characteristics or constraints of a dataset. For example, the Itakura-Saito divergence is widely used in speech processing, while the KL-divergence is the bedrock of information theory.
Key Insights and Theoretical Results
- Linearity in Disguise: Despite the complexity of the divergence functions, the bisectors of first-type diagrams are always hyperplanes. This ensures that the combinatorial complexity remains $\Theta(n^{\lceil (d+1)/2 \rceil})$, identical to the Euclidean case.
- Invariant Statistical Capacity: The authors prove that the VC-dimension of a Bregman ball is $d+1$. This implies that switching from Euclidean distance to a more complex divergence does not increase the risk of overfitting; the "statistical cost" of the model remains constant.
- Centroid Independence: A remarkable property discovered is that the "Bregman representative" (the centroid) of a set of points is simply the standard arithmetic mean, regardless of the specific Bregman divergence used. This provides a theoretical justification for why the $k$-means algorithm is so effective across diverse divergences.
Conclusion and Future Work
While the paper establishes an optimal algorithmic bound of $O(n \log n + n^{\lceil d/2 \rceil})$, the "curse of dimensionality" remains a challenge for very high-dimensional feature spaces. Additionally, for some complex generator functions, computing the inverse gradient symbolically may be impossible, requiring robust numerical approximations. Future research directions include applying these geometric structures to surface reconstruction and pattern matching in non-Euclidean statistical manifolds.
Summary updated