8481 articles  [english version]

inria-00137865, version 1

Bregman Voronoi Diagrams: Properties, Algorithms and Applications

Jean-Daniel Boissonnat () 1, Frank Nielsen () 2, Richard Nock () 3

N° RR-6154 (2007)

  • 1 :  GEOMETRICA (INRIA Sophia Antipolis)

  • INRIA France
  • 2 :  Sony Computer Science Laboratory Paris (SONY CSL-Paris)
  • http://www.csl.sony.fr/
    Sony 6, rue Amyot 75005 Paris France
  • 3 :  Centre de Recherche en Economie, Gestion, Modélisation et Informatique Appliquée (CEREGMIA)
  • http://www.ceregmia.eu/
    Université des Antilles et de la Guyane Faculté de Droit et d'Economie BP 7209 97275 Schoelcher cedex Martinique
  • Versions disponibles :  v1 (23-03-2007) v2 (19-04-2007)

    • Références bibliographiques

    • Type de publication : Rapports
    • Domaine : Informatique/Géométrie algorithmique
    • Titre : Bregman Voronoi Diagrams: Properties, Algorithms and Applications
    • Résumé : 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.
    • Classification ACM :
      G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics
      F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.2: Geometrical problems and computations
    • Langue du document : Anglais
    • Type de rapport : Rapport de recherche
    • Date de publication : 2007
    • Mots-clés : Computational Information Geometry – Voronoi diagram – Delaunay triangulation – Bregman divergence – Quantification – Sampling – Clustering
    • Date de rédaction : 2007
    • Référence interne : RR-6154

    Liste des fichiers attachés à ce document :

    PDF
    bregman.pdf(1.8 MB)
     
    • inria-00137865, version 1
    • http://hal.inria.fr/inria-00137865
    • oai:hal.inria.fr:inria-00137865
    • Contributeur : Jean-Daniel Boissonnat <>
    • Soumis le : Vendredi 23 Mars 2007, 15:59:09
    • Dernière modification le : Mercredi 28 Mars 2007, 09:25:29