Bregman Voronoi diagrams

DOI10.1007/S00454-010-9256-1MaRDI QIDQ5962350zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock

Publication date 22 September 2010

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

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

zbMATH Keywords

Bregman divergenceDelaunay triangulationVoronoi diagramLegendre transformationcomputational information geometryBregman ball

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(28)

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

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)