zbMATH — the first resource for mathematics

Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. (English) Zbl 1115.65017
The local and global convergence properties of the Lloyd algorithm [see S. Lloyd, IEEE Trans. Inf. Theory 28, 129–137 (1982; Zbl 0504.94015)] which is a popular iterative scheme for computing the centroidal Voronoi tessellations (CVTs), are studied. The new analytical results proved here [cf. Q. Du, V. Faber and M. Gunzburger, SIAM Rev. 41, 637–676 (1999; Zbl 0983.65021)] are derived through a careful utilization of the optimization properties shared by CVTs. An extension of CVTs to constrained CVTs is also presented. The study of global convergence of the Lloyd algorithm in any dimension for any smooth density is indicated as an important open problem

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
AS 136
PDF BibTeX Cite
Full Text: DOI