×

zbMATH — the first resource for mathematics

Acceleration schemes for computing centroidal Voronoi tessellations. (English) Zbl 1174.05323
Summary: Centroidal Voronoi tessellations (CVT) have diverse applications in many areas of science and engineering. The development of efficient algorithms for their construction is a key to their success in practice. In this paper, we study some new algorithms for the numerical computation of the CVT, including the Lloyd-Newton iteration and the optimization based multilevel method. Both theoretical analysis and computational simulations are conducted. Rigorous convergence results are presented and significant speedup in computation is demonstrated through the comparison with traditional methods.

MSC:
05B45 Combinatorial aspects of tessellation and tiling problems
PDF BibTeX Cite
Full Text: DOI
References:
[1] Gray, IEEE Transactions on Information Theory 44 pp 2325– (1998)
[2] Du, SIAM Review 41 pp 637– (1999)
[3] Gersho, IEEE Transactions on Information Theory 25 pp 373– (1979)
[4] Trushkin, IEEE Transactions on Information Theory 39 pp 1180– (1993) · Zbl 0801.94007
[5] Du, Applied Mathematics and Computation 133 pp 591– (2002)
[6] Ju, Parallel Computing 28 pp 1477– (2002)
[7] Ju, Computational Methods in Applied Mechanics and Engineering 191 pp 1349– (2002)
[8] Du, SIAM Journal on Scientific Computing 24 pp 1488– (2003)
[9] Cappellari, Monthly Notices of the Royal Astronomical Society 2 pp 345– (2003)
[10] Cortes, IEEE Transactions on Robotics and Automation 20 pp 243– (2004)
[11] Mendes, International Transactions in Operational Research 11 pp 1– (2004)
[12] Hiller, Computer Graphics Forum 22 pp 515– (2003)
[13] Valette, Computer Graphics Forum 23 pp 381– (2004)
[14] Wager, Journal of Royal Statistical Society B 66 pp 429– (2004)
[15] Lloyd, IEEE Transactions on Information Theory 28 pp 129– (1982)
[16] Du, SIAM Journal on Numerical Analysis (2006)
[17] Linde, IEEE Transactions on Communications 28 pp 84– (1980)
[18] Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, I, LeCam L, Neyman J (eds). 1967; 281–297.
[19] . Uniform convergence of a nonlinear energy-based multilevel quantization scheme via centroidal Voronoi tessellations. 2006, preprint.
[20] , . An energy-based multilevel quantization scheme in multidimension. 2005, preprint.
[21] . Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall: Englewood Cliffs, NJ, 1983; 86–110.
[22] . Matrix Computations. The John Hopkins University Press: Baltimore, MD, 1989.
[23] Aurenhammer, ACM Computing Surveys 23 pp 345– (1990)
[24] Fortune, Algorithmica 2 pp 153– (1987)
[25] Dwyer, Discrete and Computational Geometry 6 pp 343– (1991)
[26] , . Spatial Tessellations; Concepts and Applications of Voronoi Diagrams. Wiley: Chichester, 1992. · Zbl 0877.52010
[27] George, SIAM Journal on Numerical Analysis 10 pp 345– (1973)
[28] Brezina, SIAM Journal on Scientific Computing 22 pp 1570– (2000)
[29] Chang, SIAM Journal on Scientific Computing 24 pp 597– (2002)
[30] . Algebraic Multigrid. Multigrid Methods. Fronties in Applied Mathematics. SIAM: Philadelphia, PA, 1987; 73–130.
[31] Koren, IEEE Transactions on Information Theory 51 pp 2993– (2005)
[32] Koren, SIAM Journal on Scientific Computing (2005)
[33] Tai, Mathematics of Computation 71 pp 105– (2002)
[34] Brandt, Electronic Transactions on Numerical Analysis 10 pp 1– (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.