“On Centroidal Voronoi Tessellation – Energy Smoothness and Fast Computation” by Liu, Wang, Levy, Sun, Yan, et al. …

Centroidal Voronoi tessellation (CVT) is a particular type of Voronoi tessellation that has many applications in computational sciences and engineering, including computer graphics. The prevailing method for computing CVT is Lloyd’s method, which has linear convergence and is inefficient in practice. We develop new efficient methods for CVT computation and demonstrate the fast convergence of these methods. Specifically, we show that the CVT energy function has 2nd order smoothness for convex domains with smooth density, as well as in most situations encountered in optimization. Due to the 2nd order smoothness, it is possible to minimize the CVT energy functions using Newton-like optimization methods and expect fast convergence. We propose a quasi-Newton method to compute CVT and demonstrate its faster convergence than Lloyd’s method with various numerical examples. It is also significantly faster and more robust than the Lloyd-Newton method, a previous attempt to accelerate CVT. We also demonstrate surface remeshing as a possible application.

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617–625. 
2. Alliez, P., Colin de Verdière, É., Devillers, O., and Isenburg, M. 2003. Centroidal Voronoi diagrams for isotropic surface remeshing. Graph. Models 67, 3, 204–231. 
3. Arthur, D. and Vassilvitskii, S. 2007. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 1027–1030. 
4. Asami, Y. 1991. A note on the derivation of the first and second derivatives of objective functions in geographical optimization problems. J. Faculty Eng. The University of Tokyo(B) XLI, 1, 1–13.
5. Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469–483. 
6. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. ACM Trans. Graph. 23, 3, 905–914. 
7. Cortés, J., Martínez, S., and Bullo, F. 2005. Spatially-distributed coverage optimization and control with limited-range interactions. ESAIM Control, Optimisation Calculus Variations 11, 4, 691–719.
8. Du, Q. and Emelianenko, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numer. Linear Alg. Appl. 13, 2-3, 173–192.
9. Du, Q., Emelianenko, M., and Ju, L. 2006. Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM J. Number. Anal. 44, 1, 102–119. 
10. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41, 4, 637–676. 
11. Du, Q. and Gunzburger, M. 2002. Grid generation and optimization based on centroidal Voronoi tessellations. Appl. Math. Computat. 133, 2-3, 591–607. 
12. Du, Q., Gunzburger, M. D., and Ju, L. 2003. Constrained centroidal Voronoi tesselations for surfaces. SIAM J. Sci. Comput. 24, 5, 1488–1506. 
13. Du, Q. and Wang, D. 2003. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. Int. J. Num. Meth. Eng. 56, 9, 1355–1373.
14. Du, Q. and Wang, D. 2005a. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Sci. Comput. 26, 3, 737–761. 
15. Du, Q. and Wang, D. 2005b. The optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three-dimensional space. Comput. Math. Appl. 49, 9-10, 1355–1373. 
16. Du, Q. and Wang, X. 2004. Centroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation. In Proceedings of the IEEE Conference on Visualization. IEEE Computer Society, Los Alamitos, CA, 43–50. 
17. Fabri, A. 2001. CGAL-the computational geometry algorithm library. In Proceedings of the 10th International Meshing Roundtable. 137–142.
18. Genz, A. and Cools, R. 2003. An adaptive numerical cubature algorithm for simplices. ACM Trans. Math. Softw. 29, 3, 297–308. 
19. Gersho, A. 1979. Asymptotically optimal block quantization. IEEE Trans. Inform. Theory 25, 4, 373–380.
20. Gruber, P. M. 2004. Optimum quantization and its applications. Advances Math. 186, 2, 456–497.
21. Iri, M., Murota, K., and Ohya, T. 1984. A fast Voronoi-diagram algorithm with applications to geographical optimization problems. In Proceedings of the 11th IFIP Conference. 273–288.
22. Jiang, L., Byrd, R. H., Eskow, E., and Schnabel, R. B. 2004. A preconditioned L-BFGS algorithm with application to molecular energy minimization. Tech. rep., University of Colorado.
23. Ju, L., Du, Q., and Gunzburger, M. 2002. Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations. Parall. Comput. 28, 10, 1477–1500. 
24. Kunze, R., Wolter, F.-E., and Rausch, T. 1997. Geodesic Voronoi diagrams on parametric surfaces. In Proceedings of the Computer Graphics International. 230–237. 
25. Leibon, G. and Letscher, D. 2000. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In Proceedings of the 16th Annual Symposium on Computational Geometry (SCG). 341–349. 
26. Lin, C.-J. and Moré, J. J. 1999. Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21, 1, 24–45. 
27. Liu, D. C. and Nocedal, J. 1989. On the limited memory BFGS method for large scale optimization. Math. Prog. Series A and B 45, 3, 503–528. 
28. Lloyd, S. P. 1982. Least squares quantization in PCM. IEEE Trans. Inform. Theory 28, 2, 129–137.
29. MacQueen, J. 1966. Some methods for classification and analysis of multivariate observations. In Proceedings of the 15th Berkeley Symposium on Mathematical Statistics and Problems, Vol. 1. University of California Press, 281–297.
30. Massey, W. S. 1991. A Basic Course in Algebraic Topology. Springer.
31. McKenzie, A., Lombeyda, S. V., and Desbrun, M. 2005. Vector field analysis and visualization through variational clustering. In Proceedings of EuroVis. 29–35. 
32. More, J. J. and Thuente, D. J. 1994. Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 3, 286–307. 
33. Nocedal, J. 1980. Updating quasi-Newton matrices with limited storage. Math. Computat. 35, 773–782.
34. Nocedal, J. and Wright, S. J. 2006. Numerical Optimization, 2nd Ed. Springer.
35. Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams 2nd Ed. John Wiley&Sons, Inc.
36. Ostrovsky, R., Rabani, Y., Schulman, L. J., and Swamy, C. 2006. The effectiveness of Lloyd-type methods for the k-means problem. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 165–176. 
37. Peyré, G. and Cohen, L. 2004. Surface segmentation using geodesic centroidal tesselation. In Proceedings of the 2nd International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT). 995–1002. 
38. Schlick, T. 1992. Optimization methods in computational chemistry. In Reviews in Computational Chemistry, K. B. Lipkowitz and D. B. Boyd, Eds. John Wiley&Sons, Inc.
39. Schnabel, R. B. and Eskow, E. 1999. A revised modified Cholesky factorization algorithm. SIAM J. Optim. 9, 4, 1135–1148. 
40. Tòth, G. F. 2001. A stability criterion to the moment theorem. Studia Sci. Math. Hungar. 34, 209–224.
41. Valette, S. and Chassery, J.-M. 2004. Approximated centroidal Voronoi diagrams for uniform polygonal mesh coarsening. Comput. Graph. Forum 23, 3, 381–389.
42. Valette, S., Chassery, J.-M., and Prost, R. 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Trans. Vis. Comput. Graph. 14, 2, 369–381. 
43. Yan, D.-M., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Comput. Graph. Forum (Symposium on Geometry Processing 2009), 28 5, 1445–1455.