{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T18:58:42Z","timestamp":1783105122717,"version":"3.54.6"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T00:00:00Z","timestamp":1478822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,11,11]]},"abstract":"<jats:p>Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently out-performs the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.<\/jats:p>","DOI":"10.1145\/2980179.2982424","type":"journal-article","created":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T17:02:54Z","timestamp":1478883774000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Manifold differential evolution (MDE)"],"prefix":"10.1145","volume":"35","author":[{"given":"Yong-Jin","family":"Liu","sequence":"first","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chun-Xu","family":"Xu","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Yi","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dian","family":"Fan","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"He","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,12,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Alliez P. de Verdi\u00e8re \u00c9. C. Devillers O. and Isenburg M. 2003. Isotropic surface remeshing. In Shape Modeling International 49--58. Alliez P. de Verdi\u00e8re \u00c9. C. Devillers O. and Isenburg M. 2003. Isotropic surface remeshing. In Shape Modeling International 49--58.","DOI":"10.1109\/SMI.2003.1199601"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/131766.131772"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Boender C. G. E. and Romeijn H. E. 1995. Stochastic methods. In Handbook of Global Optimization Kluwer Academic Publishers 829--869. Boender C. G. E. and Romeijn H. E. 1995. Stochastic methods. In Handbook of Global Optimization Kluwer Academic Publishers 829--869.","DOI":"10.1007\/978-1-4615-2025-2_15"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.07.012"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2010.2059031"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2016.01.004"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501391576"},{"key":"e_1_2_2_11_1","volume-title":"Fundamentals of Computational Swarm Intelligence","author":"Engelbrecht A. P.","unstructured":"Engelbrecht , A. P. 2006. Fundamentals of Computational Swarm Intelligence . John Wiley & Sons . Engelbrecht, A. P. 2006. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2011.2160625"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Horst R. Pardalos P. M. and Thoai N. V. 2000. Introduction to Global Optimization. 2nd edition Kluwer Academic Publishers. Horst R. Pardalos P. M. and Thoai N. V. 2000. Introduction to Global Optimization. 2nd edition Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-0015-5"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_15_1","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte B.","year":"2006","unstructured":"Korte , B. , and Vygen , J . 2006 . Combinatorial Optimization: Theory and Algorithms . 3 rd edition, Springer-Verlag . Korte, B., and Vygen, J. 2006. Combinatorial Optimization: Theory and Algorithms. 3rd edition, Springer-Verlag.","edition":"3"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41095-015-0022-4"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778856"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.221"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2430342"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.28"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_24_1","volume-title":"Probability, Random Variables and Stochastic Processes","author":"Papoulis A.","unstructured":"Papoulis , A. 1991. Probability, Random Variables and Stochastic Processes . Third Edition, McGraw-Hill, Inc. Papoulis, A. 1991. Probability, Random Variables and Stochastic Processes. Third Edition, McGraw-Hill, Inc."},{"key":"e_1_2_2_25_1","volume-title":"Differential Evolution: A Practical Approach to Global Optimization","author":"Price K.","year":"2005","unstructured":"Price , K. , Storn , R. M. , and Lampinen , J. A . 2005 . Differential Evolution: A Practical Approach to Global Optimization . Springer . Price, K., Storn, R. M., and Lampinen, J. A. 2005. Differential Evolution: A Practical Approach to Global Optimization. Springer."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2015.07.003"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2011.06.005"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.53"},{"key":"e_1_2_2_29_1","volume-title":"Proc. 6th Congress on Evolutionary Computation","author":"Vesterstrom J.","unstructured":"Vesterstrom , J. , and Thomsen , R . 2004. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems . In Proc. 6th Congress on Evolutionary Computation , 1980--1987. Vesterstrom, J., and Thomsen, R. 2004. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. In Proc. 6th Congress on Evolutionary Computation, 1980--1987."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(03)90004-6"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.08.023"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2407404"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2505279"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735629"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2330574"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508379"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534161"},{"key":"e_1_2_2_38_1","volume-title":"Proc. 3rd Int. Workshop Symbolic and Numerical Algorithms on Scientific Computing.","author":"Zaharie D.","year":"2001","unstructured":"Zaharie , D. 2001 . On the explorative power of differential evolution algorithms . In Proc. 3rd Int. Workshop Symbolic and Numerical Algorithms on Scientific Computing. Zaharie, D. 2001. On the explorative power of differential evolution algorithms. In Proc. 3rd Int. Workshop Symbolic and Numerical Algorithms on Scientific Computing."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2980179.2982424","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2980179.2982424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:49:57Z","timestamp":1750218597000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2980179.2982424"}},"subtitle":["a global optimization method for geodesic centroidal voronoi tessellations on meshes"],"short-title":[],"issued":{"date-parts":[[2016,11,11]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,11,11]]}},"alternative-id":["10.1145\/2980179.2982424"],"URL":"https:\/\/doi.org\/10.1145\/2980179.2982424","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,11]]},"assertion":[{"value":"2016-12-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}