2006/01/01 by Qiang Du, Maria Emelianenko, Lili Ju · 1 citation
Engineering · Computer Science · Mathematics · #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation #Mathematical Approximation and Integration #Voronoi diagram #Centroidal Voronoi tessellation #Centroid #Mathematics #Convergence (economics) #Bounded function #Domain (mathematical analysis) #Algorithm #Mathematical optimization #Geometry #Mathematical analysis
paper · doi:10.1137/040617364
openalex publication_date 2006/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a bounded geometric domain such that the generating points of the tessellations are also the centroids (mass centers) of the corresponding Voronoi regions with respect to a given density function. Centroidal Voronoi tessellations may also be defined in more abstract and more general settings. Due to the natural optimization properties enjoyed by CVTs, they have many applications in diverse fields. The Lloyd algorithm is one of the most popular iterative schemes for computing the CVTs but its theoretical analysis is far from complete. In this paper, some new analytical results on the local and global convergence of the Lloyd algorithm are presented. These results are derived through careful utilization of the optimization properties shared by CVTs. Numerical experiments are also provided to substantiate the theoretical analysis.