Bregman Voronoi diagrams

DOI10.1007/S00454-010-9256-1zbMATH Open1201.52020DBLPjournals/dcg/BoissonnatNN10arXiv0709.2196OpenAlexW2075057405WikidataQ29544854 ScholiaQ29544854MaRDI QIDQ5962350FDOQ5962350

Authors: Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock 

Publication date: 22 September 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0709.2196

Recommendations

• On Bregman Voronoi diagrams
• Skew Jensen-Bregman Voronoi diagrams
• Voronoi diagrams and Delaunay triangulations
• scientific article; zbMATH DE number 1424293
• Voronoi diagrams of algebraic varieties under polyhedral norms

zbMATH Keywords

Bregman divergenceDelaunay triangulationVoronoi diagramLegendre transformationcomputational information geometryBregman ball

Mathematics Subject Classification ID

Combinatorial complexity of geometric structures (52C45) Discrete geometry (52C99)

Cites Work

• Visualizing hyperbolic Voronoi diagrams
• Title not available (Why is that?)
• Clustering with Bregman divergences.
• Title not available (Why is that?)
• Convex Analysis
• Manifold reconstruction in arbitrary dimensions using witness complexes
• Title not available (Why is that?)
• Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems
• Title not available (Why is that?)
• Hitting sets when the VC-dimension is small
• Concrete and abstract Voronoi diagrams
• An optimal convex hull algorithm in any fixed dimension
• Applications of random sampling in computational geometry. II
• Almost optimal set covers in finite VC-dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Power Diagrams: Properties, Algorithms and Applications
• The maximum numbers of faces of a convex polytope
• Title not available (Why is that?)
• Geometric relations among Voronoi diagrams
• Title not available (Why is that?)
• Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\)
• Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation
• A weak characterisation of the Delaunay triangulation
• Curved Voronoi diagrams
• Title not available (Why is that?)

Cited In (28)

• Extropy: complementary dual of entropy
• Conformal Flattening on the Probability Simplex and Its Applications to Voronoi Partitions and Centroids
• Monte Carlo Information-Geometric Structures
• Some universal insights on divergences for statistics, machine learning and artificial intelligence
• Voronoi polytopes for polyhedral norms on lattices
• On Bregman Voronoi diagrams
• The Kullback-Leibler divergence between lattice Gaussian distributions
• Topological data analysis with Bregman divergences
• Topological Data Analysis in Information Space.
• On Geodesic Triangles with Right Angles in a Dually Flat Space
• Voronoi diagrams of algebraic varieties under polyhedral norms
• On farthest Bregman Voronoi cells
• Smallest enclosing spheres and Chernoff points in Bregman geometry
• Classification into Kullback-Leibler balls in exponential families
• Skew Jensen-Bregman Voronoi diagrams
• Re-examination of Bregman functions and new properties of their divergences
• Uncertain Voronoi diagram
• Baseline bounded half-plane Voronoi diagram
• BOAT-SAIL VORONOI DIAGRAM AND ITS APPLICATION
• Conformal geometry of escort probability and its applications
• Semi Voronoi Diagrams
• An obstruction to Delaunay triangulations in Riemannian manifolds
• Information measures and geometry of the hyperbolic exponential families of Poincaré and hyperboloid distributions
• Manifold reconstruction using tangential Delaunay complexes
• Hyperlink regression via Bregman divergence
• Prediction in Riemannian metrics derived from divergence functions
• Approximate Bregman near neighbors in sublinear time: beyond the triangle inequality
• Income inequality measurement: a fresh look at two old issues

This page was built for publication: Bregman Voronoi diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962350)