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 various variants of Voronoi diagrams depending on the class of objects, the distance function 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 one 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 connection with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Amari, S., Nagaoka, H.: Methods of Information Geometry. Oxford University Press, London (2000). ISBN 13 9780821843024
Atkinson, C., Mitchell, F.S.: Rao’s distance measure. Sankhya Indian J. Stat., Ser. A 43, 345–365 (1981)
Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)
Aurenhammer, F., Imai, H.: Geometric relations among Voronoi diagrams. In: 4th Annual Symposium on Theoretical Aspects of Computer Sciences (STACS), pp. 53–65. Springer, London (1987)
Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J., Urrutia, G. (eds.) Handbook of Computational Geometry, pp. 201–290. Elsevier, Amsterdam (2000). Chap. V
Banerjee, A., Merugu, S., Dhillon, I.S., Ghosh, J.: Clustering with Bregman divergences. J. Mach. Learn. Res. 6, 1705–1749 (2005)
Ben-Hur, A., Horn, D., Siegelmann, H.T., Vapnik, V.: Support vector clustering. J. Mach. Learn. Res. 2, 125–137 (2002)
Boissonnat, J.-D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, New York (1998)
Boissonnat, J.-D., Wormser, C., Yvinec, M.: Curved Voronoi diagrams. In: Boissonnat, J.-D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces. Mathematics and Visualization, pp. 67–116. Springer, Berlin (2007)
Boissonnat, J.-D., Guibas, L.J., Oudot, S.Y.: Manifold reconstruction in arbitrary dimensions using witness complexes. Discrete Comput. Geom. 42(1), 37–70 (2009)
Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7, 200–217 (1967)
Brönnimann, H., Goodrich, M.T.: Optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)
Censor, Y.A., Zenios, S.A.: Parallel Optimization: Theory, Algorithms and Applications. Oxford University Press, London (1997)
Chan, T.M., Snoeyink, J., Yap, C.-K.: Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. In: SODA ’95: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 282–291. SIAM, Philadelphia (1995)
Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10, 377–409 (1993)
Chazelle, B.: The Discrepancy Method. Cambridge University Press, Cambridge (2000)
Clarkson, K., Shor, P.: Applications of random sampling in computational geometry, ii. Discrete Comput. Geom. 4, 387–421 (1989)
Csiszár, I.: Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems. Ann. Stat. 19, 2032–2066 (1991)
de Silva, V.: A weak characterisation of the Delaunay triangulation. Geom. Dedic. 135(1), 39–64 (2008)
Descartes, R.: Principia Philosophiae. Ludovicus Elzevirius, Amsterdam (1644)
Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95(2), 358–362 (2005)
Inaba, M., Imai, H.: Geometric clustering models for multimedia databases. In: Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG’98) (1998)
Inaba, M., Imai, H.: Geometric clustering for multiplicative mixtures of distributions in exponential families. In: Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG’00) (2000)
Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400. Springer, Berlin (1989). ISBN 3-540-52055-4
Labelle, F., Shewchuk, J.R.: Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In: Proc. 19th Symposium on Computational Geometry (SoCG), pp. 191–200. ACM, New York (2003)
Matousek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)
McMullen, P.: The maximum numbers of faces of a convex polytope. J. Comb. Theory, Ser. B 10, 179–184 (1971)
Nielsen, F.: Visual Computing: Geometry, Graphics, and Vision. Charles River Media/Thomson Delmar Learning (2005)
Nielsen, F., Garcia, V.: Statistical exponential families: A digest with flash cards. ar**v:0911.4863 (2009)
Nielsen, F., Nock, R.: The dual Voronoi diagrams with respect to representational Bregman divergences. In: International Symposium on Voronoi Diagrams (ISVD), DTU Lyngby, Denmark, June 2009. IEEE Press, New York (2009)
Nielsen, F., Nock, R.: Hyperbolic Voronoi diagrams made easy. ar**v:0903.3287 (March 2009)
Nock, R., Luosto, P., Kivinen, J.: Mixed Bregman clustering with approximation guarantees. In: ECML PKDD ’08: Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases—Part II, pp. 154–169. Springer, Berlin (2008)
Onishi, K., Imai, H.: Voronoi diagram in statistical parametric space by Kullback–Leibler divergence. In: Proc. 13th Symposium on Computational Geometry (SoCG), pp. 463–465. ACM, New York (1997)
Onishi, K., Imai, H.: Voronoi diagrams for an exponential family of probability distributions in information geometry. In: Japan–Korea Joint Workshop on Algorithms and Computation, pp. 1–8 (1997)
Rajan, V.T.: Optimality of the Delaunay triangulation in ℝd. Discrete Comput. Geom. 12, 189–202 (1994)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Sadakane, K., Imai, H., Onishi, K., Inaba, M., Takeuchi, F., Imai, K.: Voronoi diagrams by divergences with additive weights. In: Proc. 14th Symposium on Computational Geometry (SoCG), pp. 403–404. ACM Press, New York (1998)
Teillaud, M., Devillers, O., Meiser, S.: The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. Technical Report Rapports de Recherche No. 1620, Institut National de Recherche en Informatique et en Automatique (1992)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version appeared in the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 746–755, 2007. Related materials including demos and videos are available online at http://www.csl.sony.co.jp/person/nielsen/BregmanVoronoi/.
Rights and permissions
About this article
Cite this article
Boissonnat, JD., Nielsen, F. & Nock, R. Bregman Voronoi Diagrams. Discrete Comput Geom 44, 281–307 (2010). https://doi.org/10.1007/s00454-010-9256-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9256-1