QQ客服 官方微博 反馈留言

	Novel parallel algorithm for constructing Delaunay triangulation based on a twofold-divide-and-conquer scheme
	Wu W. Z. ; Rui Y. K. ; Su F. Z. ; Cheng L. ; Wang J. C.
	2014
关键词	adaptive subdivision parallel computing twofold-divide-and-conquer scheme Delaunay triangulation voronoi diagrams lidar data tessellation
英文摘要	To increase the efficiency when processing large data sets, a novel parallel algorithm is proposed for constructing the Delaunay triangulation of a planar point set based on a twofold-divide-and-conquer scheme. This algorithm automatically divides the planar point set into several non-overlapping subsets along the x-axis and y-axis directions alternately, according to the number of points and their spatial distribution. Next, the Guibas-Stolfi divide-and-conquer algorithm is applied to construct Delaunay sub-triangulations in each subset. Finally, the sub-triangulations are merged based on the binary tree. All three sequential steps are processed using multitasking parallel technology. Our results show that the proposed parallel algorithm is efficient for constructing the Delaunay triangulation with a good speed-up.
出处	Giscience & Remote Sensing
卷	51
期	5
页	537-554
收录类别	SCI
语种	英语
ISSN号	1548-1603
内容类型	SCI/SSCI论文
源URL	[http://ir.igsnrr.ac.cn/handle/311030/29511]
专题	地理科学与资源研究所_历年回溯文献
推荐引用方式 GB/T 7714	Wu W. Z.,Rui Y. K.,Su F. Z.,et al. Novel parallel algorithm for constructing Delaunay triangulation based on a twofold-divide-and-conquer scheme. 2014.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

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