Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from ACM papers (Siggraph, ...) can be downloaded from


“On Centroidal Voronoi Tessellation - Energy Smoothness and Fast Computation”
Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu and Chenglei Yang
Tech report - Accepted pending revisions, 2008

Abstract: TR 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 C2 smoothness in convex domains and in most other commonly encountered domains with smooth density, correcting the view in the literature that this function is non-smooth (that is, merely C0 but not C1 ). Due to its C2 smoothness, it is therefore possible to minimize the CVT energy functions using Newton-like optimization methods and expect fast convergence. We apply quasi-Newton methods to computing CVT and demonstrate their faster convergence than Lloyd's method and their better robustness than the Lloyd-Newton method, a previous attempt at CVT computation acceleration. The application of these results to surface remeshing in computer graphics is also studied.

BibTex reference

   AUTHOR     = "Yang Liu and Wenping Wang and Bruno Lévy and Feng Sun and Dong
                   -Ming Yan and Lin Lu and Chenglei Yang",
   TITLE      = "On Centroidal Voronoi Tessellation - Energy Smoothness and Fast Compu
   INSTITUTION = "Hong-Kong University and INRIA - ALICE Project Team",
   YEAR       = "2008",
   NOTE       = "Accepted pending revisions",

Supplemental material, links, hindsight ...