Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations

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 m...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on numerical analysis 2006-01, Vol.44 (1), p.102-119
Main Authors: Du, Qiang, Emelianenko, Maria, Ju, Lili
Format: Article
Language:English
Subjects:
Algorithms
Analytical estimating
Applied mathematics
Average linear density
Centroids
Critical points
Density estimation
Generators
Mathematics
Optimization
Perceptron convergence procedure
Tessellations
Voronoi diagrams
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0036-1429
1095-7170
DOI:10.1137/040617364