CASIA OpenIR  > 模式识别国家重点实验室  > 多媒体计算与图形学
 On Centroidal Voronoi Tessellation — Energy Smoothness and Fast Computation Liu, Yang; Wang, Wenping; Lévy, Bruno; Sun, Feng; Yan, Dong-Ming; Lu, Lin; Yang Chenglei Source Publication ACM Transactions on Graphics 2009 Volume 28Issue:4Pages:#101: 1-17 Other Abstract CentroidalVoronoi tessellation (CVT) is a particular type ofVoronoi 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.; CentroidalVoronoi tessellation (CVT) is a particular type ofVoronoi 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. Keyword Cvt Document Type 期刊论文 Identifier http://ir.ia.ac.cn/handle/173211/14019 Collection 模式识别国家重点实验室_多媒体计算与图形学 Recommended CitationGB/T 7714 Liu, Yang,Wang, Wenping,Lévy, Bruno,等. On Centroidal Voronoi Tessellation — Energy Smoothness and Fast Computation[J]. ACM Transactions on Graphics,2009,28(4):#101: 1-17. APA Liu, Yang.,Wang, Wenping.,Lévy, Bruno.,Sun, Feng.,Yan, Dong-Ming.,...&Yang Chenglei.(2009).On Centroidal Voronoi Tessellation — Energy Smoothness and Fast Computation.ACM Transactions on Graphics,28(4),#101: 1-17. MLA Liu, Yang,et al."On Centroidal Voronoi Tessellation — Energy Smoothness and Fast Computation".ACM Transactions on Graphics 28.4(2009):#101: 1-17.
 Files in This Item: Download All File Name/Size DocType Version Access License 2009_TOG_CVT.pdf（17775KB） 期刊论文 作者接受稿 开放获取 CC BY-NC-SA View Download
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Google Scholar Similar articles in Google Scholar [Liu, Yang]'s Articles [Wang, Wenping]'s Articles [Lévy, Bruno]'s Articles Baidu academic Similar articles in Baidu academic [Liu, Yang]'s Articles [Wang, Wenping]'s Articles [Lévy, Bruno]'s Articles Bing Scholar Similar articles in Bing Scholar [Liu, Yang]'s Articles [Wang, Wenping]'s Articles [Lévy, Bruno]'s Articles Terms of Use No data! Social Bookmark/Share
 File name: 2009_TOG_CVT.pdf Format: Adobe PDF