File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On centroidal voronoi tessellation: energy smoothness and fast computation

TitleOn centroidal voronoi tessellation: energy smoothness and fast computation
Authors
KeywordsCentroidal Voronoi Tessellation
Constrained Cvt
Lloyd's Method
Numerical Optimization
Quasi-Newton Methods
Remeshing
Issue Date2009
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://tog.acm.org
Citation
ACM Transactions on Graphics, 2009, v. 28 n. 4, article no. 101, p. 101:1-101:17 How to Cite?
AbstractCentroidal 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.
Persistent Identifierhttp://hdl.handle.net/10722/152416
ISSN
2023 Impact Factor: 7.8
2023 SCImago Journal Rankings: 7.766
ISI Accession Number ID
Funding AgencyGrant Number
Research Grant Council of Hong Kong718209
National Key Basic Research Project of China2004C318000
Hong Kong General Research Fund717808
European Research CouncilGOODSHAPE FP7-ERC-StG-205693
National Natural Research Council of China60703028
Funding Information:

The work of W. Wang is partially supported by the Research Grant Council of Hong Kong (project no.: 718209), the National Key Basic Research Project of China under 2004C318000, and a Hong Kong General Research Fund (project no.: 717808). B. Levy and Y. Liu are supported by the European Research Council (GOODSHAPE FP7-ERC-StG-205693). The work of C. Yang is supported by National Natural Research Council of China (60703028). The Rocker and Lion models are courtesy of AIM@ SHAPE Project.

References

 

DC FieldValueLanguage
dc.contributor.authorLiu, Yen_US
dc.contributor.authorWang, Wen_US
dc.contributor.authorLévy, Ben_US
dc.contributor.authorSun, Fen_US
dc.contributor.authorYan, DMen_US
dc.contributor.authorLu, Len_US
dc.contributor.authorYang, Cen_US
dc.date.accessioned2012-06-26T06:38:19Z-
dc.date.available2012-06-26T06:38:19Z-
dc.date.issued2009en_US
dc.identifier.citationACM Transactions on Graphics, 2009, v. 28 n. 4, article no. 101, p. 101:1-101:17en_US
dc.identifier.issn0730-0301en_US
dc.identifier.urihttp://hdl.handle.net/10722/152416-
dc.description.abstractCentroidal 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.en_US
dc.languageengen_US
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://tog.acm.org-
dc.relation.ispartofACM Transactions on Graphicsen_US
dc.subjectCentroidal Voronoi Tessellationen_US
dc.subjectConstrained Cvten_US
dc.subjectLloyd's Methoden_US
dc.subjectNumerical Optimizationen_US
dc.subjectQuasi-Newton Methodsen_US
dc.subjectRemeshingen_US
dc.titleOn centroidal voronoi tessellation: energy smoothness and fast computationen_US
dc.typeArticleen_US
dc.identifier.emailWang, W:wenping@cs.hku.hken_US
dc.identifier.authorityWang, W=rp00186en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1145/1559755.1559758en_US
dc.identifier.scopuseid_2-s2.0-70049086698en_US
dc.identifier.hkuros160918-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70049086698&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume28en_US
dc.identifier.issue4en_US
dc.identifier.eissn1557-7368-
dc.identifier.isiWOS:000270752100003-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridLiu, Y=36065585300en_US
dc.identifier.scopusauthoridWang, W=35147101600en_US
dc.identifier.scopusauthoridLévy, B=35264760300en_US
dc.identifier.scopusauthoridSun, F=7401804124en_US
dc.identifier.scopusauthoridYan, DM=14825994000en_US
dc.identifier.scopusauthoridLu, L=18133849600en_US
dc.identifier.scopusauthoridYang, C=7407737741en_US
dc.identifier.issnl0730-0301-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats