Back to my home page.
On Bregman Voronoi Diagrams
Frank Nielsen, Jean-Daniel Boissonnat and Richard Nock
Link to the Bregman Voronoi project home page
Abstract:
The Voronoi diagram of a point set is a fundamental geometric structure that partitions the space into elementary regions of influence defining a discrete proximity graph and dually a well-shaped Delaunay triangulation. In this paper, we investigate a framework for defining and building the Voronoi diagrams for a broad class of distortion measures called Bregman divergences, that includes not only the traditional (squared) Euclidean distance, but also various divergence measures based on entropic functions. As a by-product, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We show that for a given Bregman divergence, one can define several types of Voronoi diagrams related to each other by convex duality or embedding. Moreover, we can always compute them indirectly as power diagrams in primal or dual spaces, or directly after linearization in an extra-dimensional space as the projection of a Euclidean polytope. Finally, our paper proposes to generalize Bregman divergences to higher-order terms, called $k$-jet Bregman divergences, and touch upon their Voronoi diagrams.
Download the PDF Bregman Voronoi © ACM-SIAM Symposium on Discrete Algorithms, 2007.
BibTex entry:
@inproceedings{c-nbn-bvd-2007,
author = {Frank Nielsen and Jean-Daniel Boissonnat and Richard Nock},
title = {On Bregman Voronoi Diagrams},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2007}
}
Last updated, September 2006.