More Web Proxy on the site http://driver.im/

Article

On Bregman Voronoi diagrams

Authors:

Jean-Daniel Boissonnat,

Richard NockAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 746 - 755

Published: 07 January 2007 Publication History

Abstract

The Voronoi diagram of a point set is a fundamental geometric structure that partitions the space into elementary regions of influence defining a discrete proximity graph and dually a well-shaped Delaunay triangulation. In this paper, we investigate a framework for defining and building the Voronoi diagrams for a broad class of distortion measures called Bregman divergences, that includes not only the traditional (squared) Euclidean distance, but also various divergence measures based on entropic functions. As a by-product, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We show that for a given Bregman divergence, one can define several types of Voronoi diagrams related to each other by convex duality or embedding. Moreover, we can always compute them indirectly as power diagrams in primal or dual spaces, or directly after linearization in an extra-dimensional space as the projection of a Euclidean polytope. Finally, our paper proposes to generalize Bregman divergences to higher-order terms, called κ-jet Bregman divergences, and touch upon their Voronoi diagrams.

References

[1]

S. Amari and H. Nagaoka, Methods of Information Geometry, Oxford University Press, 2000.

[2]

F. Aurenhammer, Power diagrams: Properties, algorithms and applications, SIAM Journal of Computing, 16 (1987), pp. 78--96.

Digital Library

[3]

F. Aurenhammer and R. Klein, Voronoi Diagrams, Handbook of Computational Geometry, J. Sack and G. Urrutia, Eds., Elsevier, 2000, pp. 201--290.

[4]

A. Banerjee, S. Merugu, I. S. Dhillon, and J. Ghosh, Clustering with Bregman divergences, Journal of Machine Learning Research, 6 (2005), pp. 1705--1749.

Digital Library

[5]

J.-D. Boissonnat and M. Karavelas, On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres, Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, 2003, pp. 305--312.

Digital Library

[6]

J.-D. Boissonnat, C. Wormser, and M. Yvinec, Anisotropic diagrams: Labelle Shewchuk approach revisited, 17th Canadian Conference on Computational Geometry, 2005, pp. 266--269.

[7]

J.-D. Boissonnat and M. Yvinec, Algorithmic Geometry, Cambridge University Press, 1998.

Digital Library

[8]

L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR, Computational Mathematics and Mathematical Physics, 7 (1967), pp. 200--217.

[9]

K. Q. Brown, Voronoi diagrams from convex hulls, Inf. Process. Lett., 9 (1979), pp. 223--228.

[10]

B. Chazelle, An optimal convex hull algorithm in any fixed dimension, Discrete Computational Geometry, 10 (1993), pp. 377--409.

[11]

Q. Du, V. Faber and M. Gunzburger, Centroidal Voronoi Tesselations: Applications and Algorithms, SIAM Review, 41 (1999), pp. 637--676.

Digital Library

[12]

Y. Eldar, M. Lindenbaum, M. Porat and Y. Y. Zeevi, The Farthest Point Strategy for Progressive Image Sampling, IEEE Trans, on Image Processing, 6(9) (1997), pp. 1305--1315.

Digital Library

[13]

M. Herbster and M. Warmuth, Tracking the best regressor, Proc. 11th Conference on Computational Learning Theory, 1998, pp. 24--31.

Digital Library

[14]

R. Klein, Concrete and Abstract Voronoi Diagrams, vol. 400 of Lecture Notes in Computer Science, Springer, 1989. ISBN 3-540-52055-4.

[15]

G. Leibon and D. Letscher, Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, Proc. 16th Symposium on Computational Geometry, 2000, pp. 341--349.

Digital Library

[16]

S. P. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory (1982), pp. 129--137

[17]

P. McMullen, The maximum numbers of faces of a convex polytope, J. Combinatorial Theory, Ser. B, 10 (1971), pp. 179--184.

[18]

F. Nielsen, J.-D. Boissonnat, and R. Nock, On Bregman Voronoi diagrams, INRIA technical report, 2006.

[19]

R. Nock and F. Nielsen, Fitting the smallest enclosing Bregman ball, 16th European Conference on Machine Learning, 2005, pp. 649--656.

Digital Library

[20]

K. Onishi and H. Imai, Voronoi diagram in statistical parametric space by Kullback-Leibler divergence, in Proc. 13th Symposium on Computational Geometry, 1997, pp. 463--465.

Digital Library

[21]

K. Onishi and N. Takayama, Construction of Voronoi diagram on the upper half-plane, IEICE Transactions, 79--A (1996), pp. 533--539.

[22]

V. T. Rajan, Optimality of the Delaunay triangulation in R^d, Disc. & Comp. Geom., 12 (1994), pp. 189--202.

[23]

J. Ruppert, A Delaunay Refinement Algorithm for Quality S-Dimensional Mesh Generation, J. Algorithms, 18 (1995), pp. 548--585.

Digital Library

[24]

K. Sadakane, H. Imai, K. Onishi, M. Inaba, F. Takeuchi, and K. Imai, Voronoi diagrams by divergences with additive weights, Proc. 14th Symposium on Computational Geometry, 1998, pp. 403--404.

Digital Library

[25]

M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom., 12 (1994), pp. 327--345.

Cited By

Gyongyosi LImre S(2014)Geometrical analysis of physically allowed quantum cloning transformations for quantum cryptographyInformation Sciences: an International Journal10.1016/j.ins.2014.07.010285:C(1-23)Online publication date: 20-Nov-2014
https://dl.acm.org/doi/10.1016/j.ins.2014.07.010
Gyongyosi LImre S(2013)Algorithmic superactivation of asymptotic quantum capacity of zero-capacity quantum channelsInformation Sciences: an International Journal10.1016/j.ins.2012.08.008222(737-753)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2012.08.008
Nielsen F(2013)Pattern learning and recognition on statistical manifoldsProceedings of the Second international conference on Similarity-Based Pattern Recognition10.1007/978-3-642-39140-8_1(1-25)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39140-8_1
Show More Cited By

On Bregman Voronoi diagrams
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Bregman Voronoi Diagrams

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 ...
Skew jensen-bregman voronoi diagrams
Transactions on Computational Science XIV

A Jensen-Bregman divergence is a distortion measure defined by a Jensen convexity gap induced by a strictly convex functional generator. Jensen-Bregman divergences unify the squared Euclidean and Mahalanobis distances with the celebrated information-...
Jensen-Bregman Voronoi Diagrams and Centroidal Tessellations
ISVD '10: Proceedings of the 2010 International Symposium on Voronoi Diagrams in Science and Engineering

The Jensen-Bregman divergence is a distortion measure defined by the Jensen difference provided by a strictly convex function. Jensen-Bregman divergences extend the well-known Jensen-Shannon divergence by allowing to choose an arbitrary convex function ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
461
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gyongyosi LImre S(2014)Geometrical analysis of physically allowed quantum cloning transformations for quantum cryptographyInformation Sciences: an International Journal10.1016/j.ins.2014.07.010285:C(1-23)Online publication date: 20-Nov-2014
https://dl.acm.org/doi/10.1016/j.ins.2014.07.010
Gyongyosi LImre S(2013)Algorithmic superactivation of asymptotic quantum capacity of zero-capacity quantum channelsInformation Sciences: an International Journal10.1016/j.ins.2012.08.008222(737-753)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2012.08.008
Nielsen F(2013)Pattern learning and recognition on statistical manifoldsProceedings of the Second international conference on Similarity-Based Pattern Recognition10.1007/978-3-642-39140-8_1(1-25)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39140-8_1
Tanuma TImai HMoriyama S(2011)Revisiting hyperbolic voronoi diagrams in two and higher dimensions from theoretical, applied and generalized viewpointsTransactions on Computational Science XIV10.5555/2172419.2172420(1-30)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2172419.2172420
Gyongyosi LImre S(2011)Channel capacity restoration of noisy optical quantum channelsProceeding of 10th WSEAS international conference on electronics, hardware, wireless and optical communications, and 10th WSEAS international conference on signal processing, robotics and automation, and 3rd WSEAS international conference on nanotechnology, and 2nd WSEAS international conference on Plasma-fusion-nuclear physics10.5555/1959586.1959640(283-288)Online publication date: 20-Feb-2011
https://dl.acm.org/doi/10.5555/1959586.1959640
Setter OSharir MHalperin D(2010)Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in spaceTransactions on computational science IX10.5555/1986573.1986574(1-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986573.1986574
Setter OSharir MHalperin D(2010)Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in spaceTransactions on computational science IX10.5555/1980587.1980588(1-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1980587.1980588
Wang XFyfe C(2010)Independent component analysis using bregman divergencesProceedings of the 23rd international conference on Industrial engineering and other applications of applied intelligent systems - Volume Part II10.5555/1945847.1945922(627-636)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.5555/1945847.1945922
Lee D(2010)Computational geometry IIAlgorithms and theory of computation handbook10.5555/1882723.1882725(2-2)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882725
Nielsen FPiro PBarlaud M(2009)Bregman vantage point trees for efficient nearest neighbor queriesProceedings of the 2009 IEEE international conference on Multimedia and Expo10.5555/1698924.1699139(878-881)Online publication date: 28-Jun-2009
https://dl.acm.org/doi/10.5555/1698924.1699139
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents