{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T23:33:05Z","timestamp":1791502385165,"version":"4.3.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2004C318000"],"award-info":[{"award-number":["2004C318000"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["GOODSHAPE FP7-ERC-StG-205693"],"award-info":[{"award-number":["GOODSHAPE FP7-ERC-StG-205693"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Natural Research Council of China","award":["60703028"],"award-info":[{"award-number":["60703028"]}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["718209"],"award-info":[{"award-number":["718209"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["717808"],"award-info":[{"award-number":["717808"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1559755.1559758","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T08:53:03Z","timestamp":1252399983000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":292,"title":["On centroidal voronoi tessellation\u2014energy smoothness and fast computation"],"prefix":"10.1145","volume":"28","author":[{"given":"Yang","family":"Liu","sequence":"first","affiliation":[{"name":"Project ALICE, INRIA, Villers les Nancy, France and The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenping","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruno","family":"L\u00e9vy","sequence":"additional","affiliation":[{"name":"Project ALICE, INRIA, Villers les Nancy, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feng","family":"Sun","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dong-Ming","family":"Yan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lin","family":"Lu","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chenglei","family":"Yang","sequence":"additional","affiliation":[{"name":"Shandong University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,9,8]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073238"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2004.06.007"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 1027--1030","author":"Arthur D.","unstructured":"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 . 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."},{"key":"e_1_2_2_4_1","first-page":"1","article-title":"A note on the derivation of the first and second derivatives of objective functions in geographical optimization problems","author":"Asami Y.","year":"1991","unstructured":"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 . 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.","journal-title":"J. Faculty Eng. The University of Tokyo(B)"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015817"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1051\/cocv:2005024"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.476"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/040617364"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-3003(01)00260-0"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501391576"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.616"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503428527"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2004.12.008"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2004.13"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 10th International Meshing Roundtable. 137--142","author":"Fabri A.","year":"2001","unstructured":"Fabri , A. 2001 . CGAL-the computational geometry algorithm library . In Proceedings of the 10th International Meshing Roundtable. 137--142 . Fabri, A. 2001. CGAL-the computational geometry algorithm library. In Proceedings of the 10th International Meshing Roundtable. 137--142."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/838250.838254"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056067"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.07.017"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 11th IFIP Conference. 273--288","author":"Iri M.","unstructured":"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 . 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."},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.21236\/ADA444850"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(02)00151-5"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the Computer Graphics International. 230--237","author":"Kunze R.","unstructured":"Kunze , R. , Wolter , F.-E. , and Rausch , T . 1997. Geodesic Voronoi diagrams on parametric surfaces . In Proceedings of the Computer Graphics International. 230--237 . Kunze, R., Wolter, F.-E., and Rausch, T. 1997. Geodesic Voronoi diagrams on parametric surfaces. In Proceedings of the Computer Graphics International. 230--237."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336221"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597327334"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589116"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the 15th Berkeley Symposium on Mathematical Statistics and Problems","volume":"1","author":"MacQueen J.","year":"1966","unstructured":"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. 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."},{"key":"e_1_2_2_30_1","volume-title":"A Basic Course in Algebraic Topology","author":"Massey W. S.","unstructured":"Massey , W. S. 1991. A Basic Course in Algebraic Topology . Springer . Massey, W. S. 1991. A Basic Course in Algebraic Topology. Springer."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2384060.2384066"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/192115.192132"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1980-0572855-7"},{"key":"e_1_2_2_34_1","unstructured":"Nocedal J. and Wright S. J. 2006. Numerical Optimization 2nd Ed. Springer.  Nocedal J. and Wright S. J. 2006. Numerical Optimization 2nd Ed. Springer."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.75"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018408.1018731"},{"key":"e_1_2_2_38_1","volume-title":"Reviews in Computational Chemistry","author":"Schlick T.","unstructured":"Schlick , T. 1992. Optimization methods in computational chemistry . In Reviews in Computational Chemistry , K. B. Lipkowitz and D. B. Boyd, Eds. John Wiley &amp;Sons, Inc. Schlick, T. 1992. Optimization methods in computational chemistry. In Reviews in Computational Chemistry, K. B. Lipkowitz and D. B. Boyd, Eds. John Wiley&amp;Sons, Inc."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349833266X"},{"key":"e_1_2_2_40_1","first-page":"209","article-title":"A stability criterion to the moment theorem. Studia Sci","volume":"34","author":"T\u00f2th G. F.","year":"2001","unstructured":"T\u00f2th , G. F. 2001 . A stability criterion to the moment theorem. Studia Sci . Math. Hungar. 34 , 209 -- 224 . T\u00f2th, G. F. 2001. A stability criterion to the moment theorem. Studia Sci. Math. Hungar. 34, 209--224.","journal-title":"Math. Hungar."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2004.00769.x"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70430"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Yan D.-M. L\u00e9vy 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.   Yan D.-M. L\u00e9vy 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.","DOI":"10.1111\/j.1467-8659.2009.01521.x"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1559755.1559758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1559755.1559758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:29:57Z","timestamp":1750238997000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1559755.1559758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1559755.1559758"],"URL":"https:\/\/doi.org\/10.1145\/1559755.1559758","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}