IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Weak global convergence of the Lloyd method for computing centroidal Voronoi tessellations in Rd


A 2007 Preprint by M. Emelianenko, L. Ju, and A. Rand

  • 2007:07
  • Centroidal Voronoi tessellations (CVTs) are special Voronoi tessellations of a domain $\Omega\in{R^d}$ having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function $\rho\geq0$, of the corresponding Voronoi cells. CVTs and CVT-based methodologies have been very useful across many fields in sciences and engineering. Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs, but until now its global convergence in higher dimensional spaces ($d>1$) remained open. In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is non-degenerate provided that $\Omega$ is a convex and bounded set, and ρ belongs to $L _ 1(\Omega)$ and is positive almost everywhere. It guarantees that the Lloyd iteration is weakly globally convergent to the set of non-degenerate critical points of the so-called quantization energy. Practically, this ensures that any limit point of the algorithm does generate a CVT. The convergence properties of the Lloyd iteration mentioned above have been conjectured and discussed in earlier investigations, but they have never until now been rigorously justified. The results presented in this paper extend the convergence theory related to the methods of constructing CVTs and hence should be of interest to both mathematical and engineering communities.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC