A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space

Most of the traditional algorithms for the generation of spherical Voronoi diagram are in vector mode and only good for point sets. Recently, approximate raster-based algorithms that easily generate spherical Voronoi diagrams of point, line, and area sets have been proposed. However, almost all these raster-based algorithms are based on dilation operations. Dilation errors however, increase with the growth of dilation steps and are irregularly distributed. To overcome these deficiencies, a parallel algorithm for generating spherical Voronoi diagrams based on the discrete characteristics of a Quaternary Triangular Mesh (QTM) and the multi-thread principle of GPU (Graphics Processing Unit) is proposed. An algorithm for extracting Voronoi boundaries was also developed. Experiments were conducted using C++ and Compute Unified Device Architecture (CUDA). Results show that this algorithm can handle line sets and area sets as well as point sets and the Voronoi error can be limited within two grids. Additionally, efficiency when generating spherical Voronoi diagrams was improved greatly by using GPU parallel computation.