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
2009
发表期刊ACM Transactions on Graphics
卷号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浏览 下载
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Liu, Yang]的文章
[Wang, Wenping]的文章
[Lévy, Bruno]的文章
百度学术
百度学术中相似的文章
[Liu, Yang]的文章
[Wang, Wenping]的文章
[Lévy, Bruno]的文章
必应学术
必应学术中相似的文章
[Liu, Yang]的文章
[Wang, Wenping]的文章
[Lévy, Bruno]的文章
相关权益政策
暂无数据
收藏/分享
文件名: 2009_TOG_CVT.pdf
格式: Adobe PDF
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。