The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1967) · Cited by 23,719
Least squares quantization in PCM
Lloyd, S. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056489 · Cited by 15,836
Algorithm AS 136: A K-Means Clustering Algorithm
Hartigan, J. A., & Wong, M. A. (1979) · Applied Statistics · doi:10.2307/2346830 · Cited by 14,523
An Algorithm for Vector Quantizer Design
Linde, Y., Buzo, A., & Gray, R. (1980) · IEEE Transactions on Communications · doi:10.1109/tcom.1980.1094577 · Cited by 7,201
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,003
An efficient k-means clustering algorithm: analysis and implementation
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1017616 · Cited by 5,660
Linear and nonlinear programming.
(1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90092-3 · Cited by 4,805
Spatial Tessellations: Concepts and Applications of Voronoi Diagrams
Okabe, A., Boots, B. N., & Sugihara, K. (1992) · Cited by 3,546
Coverage Control for Mobile Sensing Networks
Cortes, J., Martinez, S., Karatas, T., & Bullo, F. (2004) · IEEE Transactions on Robotics and Automation · doi:10.1109/tra.2004.824698 · Cited by 2,710
Centroidal Voronoi Tessellations: Applications and Algorithms
Du, Q., Faber, V., & Gunzburger, M. (1999) · SIAM Review · doi:10.1137/s0036144599352836 · Cited by 2,244
Self-citationGray, R. M., & Neuhoff, D. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720541 · Cited by 1,642
Adaptive spatial binning of integral-field spectroscopic data using Voronoi tessellations
Cappellari, M., & Copin, Y. (2003) · Monthly Notices of the Royal Astronomical Society · doi:10.1046/j.1365-8711.2003.06541.x · Cited by 1,309
Variational shape approximation
Cohen-Steiner, D., Alliez, P., & Desbrun, M. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015817 · Cited by 642
Color image quantization for frame buffer display
Heckbert, P. (1982) · ACM SIGGRAPH Computer Graphics · doi:10.1145/965145.801294 · Cited by 549
Constrained Centroidal Voronoi Tessellations for Surfaces
Du, Q., Gunzburger, M. D., & Ju, L. (2003) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827501391576 · Cited by 245
Self-citationProbabilistic methods for centroidal Voronoi tessellations and their parallel implementations
Ju, L., Du, Q., & Gunzburger, M. (2002) · Parallel Computing · doi:10.1016/s0167-8191(02)00151-5 · Cited by 192
Self-citationGlobal convergence and empirical consistency of the generalized Lloyd algorithm
Sabin, M. J., & Gray, R. M. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057168 · Cited by 139
Locally optimal block quantizer design
Gray, R. M., Kieffer, J. C., & Linde, Y. (1980) · Information and Control · doi:10.1016/s0019-9958(80)90313-7 · Cited by 136
Acceleration schemes for computing centroidal Voronoi tessellations
Du, Q., & Emelianenko, M. (2006) · Numerical Linear Algebra with Applications · doi:10.1002/nla.476 · Cited by 65
Self-citationCentroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation
Du, Q., & Wang, X. (2005) · Visualization · doi:10.1109/visual.2004.13 · Cited by 38
Self-citation
Cited by
On centroidal voronoi tessellation—energy smoothness and fast computation
Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., & Yang, C. (2009) · ACM Transactions on Graphics · doi:10.1145/1559755.1559758 · Cited by 341
Quad‐Mesh Generation and Processing: A Survey
Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., & Zorin, D. (2013) · Computer Graphics Forum · doi:10.1111/cgf.12014 · Cited by 323
Metadata
- Authors
- Du, Q., Emelianenko, M., & Ju, L.
- Venue
- SIAM Journal on Numerical Analysis
- Published
- 2006-01
- Volume
- 44
- Issue
- 1
- Pages
- 102-119
- ISSN
- 0036-1429 (ISSN-L)
- 1095-7170
- OpenAlex
- W2065978712
- Cited by
- 305
- References
- 20
- FWCI
- 19.38
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.