Acceleration schemes for computing centroidal Voronoi tessellations

Centroidal Voronoi tessellations (CVT) have diverse applications in many areas of science and engineering. The development of efficient algorithms for their construction is a key to their success in practice. In this paper, we study some new algorithms for the numerical computation of the CVT, inclu...

Full description

Saved in:
Bibliographic Details
Published in:Numerical linear algebra with applications 2006-03, Vol.13 (2-3), p.173-192
Main Authors: Du, Qiang, Emelianenko, Maria
Format: Article
Language:English
Subjects:
centroidal Voronoi tessellations
computational algorithms
Lloyd's method
multilevel method
Newton's method
uniform convergence
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 (CVT) have diverse applications in many areas of science and engineering. The development of efficient algorithms for their construction is a key to their success in practice. In this paper, we study some new algorithms for the numerical computation of the CVT, including the Lloyd–Newton iteration and the optimization based multilevel method. Both theoretical analysis and computational simulations are conducted. Rigorous convergence results are presented and significant speedup in computation is demonstrated through the comparison with traditional methods. Copyright © 2006 John Wiley & Sons, Ltd.
ISSN:1070-5325
1099-1506
DOI:10.1002/nla.476