Yang Liu
Wenping Wang
Dong-Ming Yan
Lin Lu
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
pdf
a101-liu-apndx.pdf (115.9 KB)
Online appendix to on centroidal voronoi tessellation—energy smoothness and fast computation. The appendix supports the information on article 101.
- Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469--483. Google ScholarDigital Library
- Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. ACM Trans. Graph. 23, 3, 905--914. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Du, Q. and Emelianenko, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numer. Linear Alg. Appl. 13, 2-3, 173--192.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41, 4, 637--676. Google ScholarDigital Library
- Du, Q. and Gunzburger, M. 2002. Grid generation and optimization based on centroidal Voronoi tessellations. Appl. Math. Computat. 133, 2-3, 591--607. Google ScholarDigital Library
- Du, Q., Gunzburger, M. D., and Ju, L. 2003. Constrained centroidal Voronoi tesselations for surfaces. SIAM J. Sci. Comput. 24, 5, 1488--1506. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Du, Q. and Wang, D. 2005a. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Sci. Comput. 26, 3, 737--761. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Fabri, A. 2001. CGAL-the computational geometry algorithm library. In Proceedings of the 10th International Meshing Roundtable. 137--142.Google Scholar
- Genz, A. and Cools, R. 2003. An adaptive numerical cubature algorithm for simplices. ACM Trans. Math. Softw. 29, 3, 297--308. Google ScholarDigital Library
- Gersho, A. 1979. Asymptotically optimal block quantization. IEEE Trans. Inform. Theory 25, 4, 373--380.Google ScholarDigital Library
- Gruber, P. M. 2004. Optimum quantization and its applications. Advances Math. 186, 2, 456--497.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Ju, L., Du, Q., and Gunzburger, M. 2002. Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations. Parall. Comput. 28, 10, 1477--1500. Google ScholarDigital Library
- Kunze, R., Wolter, F.-E., and Rausch, T. 1997. Geodesic Voronoi diagrams on parametric surfaces. In Proceedings of the Computer Graphics International. 230--237. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Lin, C.-J. and Moré, J. J. 1999. Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21, 1, 24--45. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Lloyd, S. P. 1982. Least squares quantization in PCM. IEEE Trans. Inform. Theory 28, 2, 129--137.Google ScholarDigital Library
- 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.Google Scholar
- Massey, W. S. 1991. A Basic Course in Algebraic Topology. Springer.Google Scholar
- McKenzie, A., Lombeyda, S. V., and Desbrun, M. 2005. Vector field analysis and visualization through variational clustering. In Proceedings of EuroVis. 29--35. Google ScholarDigital Library
- More, J. J. and Thuente, D. J. 1994. Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 3, 286--307. Google ScholarDigital Library
- Nocedal, J. 1980. Updating quasi-Newton matrices with limited storage. Math. Computat. 35, 773--782.Google ScholarCross Ref
- Nocedal, J. and Wright, S. J. 2006. Numerical Optimization, 2nd Ed. Springer.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Schnabel, R. B. and Eskow, E. 1999. A revised modified Cholesky factorization algorithm. SIAM J. Optim. 9, 4, 1135--1148. Google ScholarDigital Library
- Tòth, G. F. 2001. A stability criterion to the moment theorem. Studia Sci. Math. Hungar. 34, 209--224.Google Scholar
- Valette, S. and Chassery, J.-M. 2004. Approximated centroidal Voronoi diagrams for uniform polygonal mesh coarsening. Comput. Graph. Forum 23, 3, 381--389.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- On centroidal voronoi tessellation—energy smoothness and fast computation
Recommendations
Lp Centroidal Voronoi Tessellation and its applications
This paper introduces Lp-Centroidal Voronoi Tessellation (Lp-CVT), a generalization of CVT that minimizes a higher-order moment of the coordinates on the Voronoi cells. This generalization allows for aligning the axes of the Voronoi cells with a ...
Fast Methods for Computing Centroidal Voronoi Tessellations
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 ...
GPU-Assisted Computation of Centroidal Voronoi Tessellation
Centroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd's method, and recently the L-BFGS method is shown to be faster than Lloyd's method for computing the CVT. However, ...
Comments