Yang Liu^{1,2}, Wenping Wang^{1}, Bruno Lévy^{2}, Feng Sun^{1}, DongMing Yan^{1}, Lin Lu^{1}, Chenglei Yang^{3}
^{1}Department of Computer Science, The University of Hong Kong
^{2}Project ALICE, INRIA, Villers les Nancy, France
^{3}School of Computer Science and Technology, Shandong
University, China
Lion model (# of faces: 50,000, # of vertices: 25,002, # of seeds: 25,002). Left: The input mesh; Left middle: the initial Voronoi diagram; Right middle:: CCVT computed by LBFGS; Right: the triangle mesh dual to CCVT. 
Rocker model (# of faces: 11,316, # of vertices: 5,658, # of seeds: 5,658). Left: The input mesh; Left middle: the initial Voronoi diagram; Right middle:: CCVT computed by LBFGS; Right: the triangle mesh dual to CCVT. 
Abstract: Centroidal Voronoi tessellation (CVT) is a fundamental geometric structure that finds many applications in computational science and engineering, including computer graphics. The prevailing method for computing CVT is Lloyd's method, which has linear convergence and is inefficient in practice. Our goal is to develop efficient methods for CVT computation, justify the fast convergence of these methods theoretically and demonstrate their superiority with experimental examples in various cases. Specifically, it is shown that the CVT energy function has C^{2} smoothness in convex domains and in most other commonly encountered domains with smooth density, correcting the view in the literature that this function is nonsmooth (that is, merely C^{0} but not C^{1}). Due to its C^{2} smoothness, it is therefore possible to minimize the CVT energy functions using Newtonlike optimization methods and expect fast convergence. We apply quasiNewton methods to computing CVT and demonstrate their faster convergence than Lloyd's method and their better robustness than the LloydNewton method, a previous attempt at CVT computation acceleration. The application of these results to surface remeshing in computer graphics is also studied. 
PDF (8.91M) See also CVT page at Alice@loria
