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

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

A parallel algorithm for generating Voronoi diagrams based onpoint-set adaptive grouping

This paper presents a parallel algorithm for generating Voronoi diagrams based on point-set adaptive grouping. The algorithm works in the following steps. Firstly, the method of binary tree spitting is adopted to adaptively divide the planar point-set into groups. The points within each group independently generate Voronoi diagram, named the Voronoi sub-diagram. Then, the boundary points in each group are collected to construct another Voronoi diagram, called boundary-point Voronoi diagram. Finally, for each boundary point, two polygons in which the boundary point is located are extracted respectively from the Voronoi sub-diagram and the boundary-point Voronoi diagram. These two kinds of polygons are merged to ultimately realize the combination of Voronoi sub-diagram. Considering that the generation of Voronoi sub-diagram is the most time consuming part and each sub-diagram is independent from each other, the parallel computing technique is used to accelerate the generation of Voronoi sub-diagram. Theoretical analysis and tests show that this proposed algorithm is an efficient method of generating Voronoi diagram.