Computing 2D Periodic Centroidal Voronoi Tessellation

	Computing 2D Periodic Centroidal Voronoi Tessellation
	Yan, Dong-Ming; Wang, Kai; Lévy, Bruno; Alonso Laurent
	2011
会议名称	8th International Symposium on Voronoi Diagrams in Science and Engineering - ISVD 2011
会议日期	2011-06
会议地点	Qing Dao
摘要	In this paper, we propose an efficient algorithm to compute the centroidal Voronoi tessellation in 2D periodic space. We first present a simple algorithm for constructing the periodic Voronoi diagram (PVD) from a Euclidean Voronoi diagram. The presented PVD algorithm considers only a small set of periodic copies of the input sites, which is more efficient than previous approaches requiring full copies of the sites (9 in 2D and 27 in 3D). The presented PVD algorithm is applied in a fast Newton-based framework for computing the centroidal Voronoi tessellation (CVT). We observe that full-hexagonal patterns can be obtained via periodic CVT optimization attributed to the convergence of the Newton-based CVT computation.
关键词	Cvt
文献类型	会议论文
条目标识符	http://ir.ia.ac.cn/handle/173211/14015
专题	多模态人工智能系统全国重点实验室_多媒体计算
推荐引用方式 GB/T 7714	Yan, Dong-Ming,Wang, Kai,Lévy, Bruno,et al. Computing 2D Periodic Centroidal Voronoi Tessellation[C],2011.