Computation and properties of Centroidal Voronoi Tessellation

Centroidal Voronoi Tessellation (CVT) is a variational framework of computing an optimal geometric structure based on the Voronoi Diagram, and is used in many applications of computer graphics and geometric processing. I will present several recent results on CVT. First it will be shown that the objective function of the CVT problem in Euclidean space of dimension two or higher is almost always $C^2$, contrary to the common belief that it is a nonsmooth piecewise function. Based on the $C^2$ smoothness of its objective function, a Newton-like method for computing CVT is presented that is one order of magnitude faster than the prevailing Lloyd method. Then from an empirical point of view, I will discuss the extremal properties of the CVT problem and the associated challenges in computing acceptable local minimum points. Finally, several extensions and applications of the CVT problem relevant to shape modeling will be presented, including CVT-based triangulation on surfaces and variational computation with Power Diagrams. This talk is based on a collection of joined works with Yang Liu, Bruno Levy, Feng Sun, Dongming Yan, Lu Lin.