Published

Fast Methods for Computing Centroidal Voronoi Tessellations

James Hateley, Huayi Wei and Long Chen

Journal of Scientific Computing, 63(1), 185-212, 2015

pdf   Bibtex

ABSTRACT:

 A Centroidal Voronoi Tessellation (CVT) is a Voronoi
tessellation in which the generators are the centroids for each
Voronoi region. CVTs have many applications to computer graphics,
image processing, data compression, mesh generation, and optimal
quantization. Lloyd's method, the most widely method used to generate
CVTs, converges very slowly for larger scale problems. Recently
quasi-Newton methods using the Hessian of the energy associated as a
preconditioner are developed to speed up the rate of convergence. In
this work a graph Laplacian preconditioner and a two-grid method are
used to speed up quasi-Newton schemes.  The proposed graph Laplacian
is always symmetric, positive definite and easy to assemble, while the
Hessian, in general, may not be positive definite nor easy to
assemble. Therefore the graph Laplacian works as a better
preconditioner than the Hessian which needs modification to be used a
preconditioner. The two-grid method is used to generate a better
initial guess to further speed up the convergence. Numerical tests
show that our preconditioned optimization methods converges fast and
has nearly linear complexity.