一种基于点集自适应分组构建Voronoi图的并行算法

摘要：

论文提出一种基于点集自适应分组构建Voronoi图的并行算法,其基本思路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成Voronoi图,称为Voronoi子图；提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi图；最后,针对每个边界点,提取其位于Voronoi子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi多边形的合并,最终实现子网的合并.考虑到算法耗时主要在分组点集的Voronoi图生成,而各分组的算法实现不受其他分组影响,采用并行计算技术加速分组点集的Voronoi图生成.理论分析和测试表明,该算法是一个效率较高的Voronoi图生成并行算法.

关键词：Voronoi图、并行算法、自适应分组、计算几何

所属期刊栏目：33

分类号：TP391(计算技术、计算机技术)

资助基金：国家科技支撑计划资助项目2012BAH28B02

在线出版日期：2013-01-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：7-13