Bregman Voronoi Diagrams: Properties, Algorithms and Applications

Understand

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.