Knowledge Commons of Institute of Automation,CAS
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 | |
发表期刊 | ACM Transactions on Graphics |
2009 | |
卷号 | 28期号:4页码:#101: 1-17 |
其他摘要 |
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. |
关键词 | Cvt |
文献类型 | 期刊论文 |
条目标识符 | http://ir.ia.ac.cn/handle/173211/14019 |
专题 | 多模态人工智能系统全国重点实验室_多媒体计算 |
推荐引用方式 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. |
条目包含的文件 | 下载所有文件 | |||||
文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
2009_TOG_CVT.pdf(17775KB) | 期刊论文 | 作者接受稿 | 开放获取 | CC BY-NC-SA | 浏览 下载 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论