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 PublicationACM Transactions on Graphics
2009
Volume28Issue: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.
KeywordCvt
Document Type期刊论文
Identifierhttp://ir.ia.ac.cn/handle/173211/14019
Collection模式识别国家重点实验室_多媒体计算与图形学
Recommended Citation
GB/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-SAView 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
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.