A parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping

摘要

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point-set adaptiverngrouping. The binary tree splitting method is used to adaptively group the point set in the plane andrnconstruct sub-Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in eachrngroup consumes the majority of time and that construction within one group does not affect that in otherrngroups, the use of a parallel algorithm is suitable. After constructing the sub-Voronoi diagrams, we extractedrnthe boundary points of the four sides of each sub-group and used to construct boundary site Voronoirndiagrams. Finally, the sub-Voronoi diagrams containing each boundary point are merged with therncorresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experimentsrndemonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function ofrnthe size of the point set, the number of processors, the average number of points in each block, and thernnumber of boundary points.