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

Abstract: 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.

Key words: Voronoi diagrams, parallel algorithms, adaptive group, computational geometry