Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram

A spherical Voronoi diagram of point sets,line sets and area sets can be well handled byGDG-based(GDG:Global Discrete Grid)algorithms.However,the grid data volume and the timeconsumed for generating spherical Voronoi diagrams increases exponentially with the growth of theGDG levels,which leads to lower efficiency at higher levels.To overcome these deficiencies,a multi-level QTM-based(QTM:Quaternary Triangular Mesh)algorithm is proposed.Firstly,a sphericalVoronoi diagram is generated in a lower level.Then,the triangles that form the Voronoi boundariesare subdivided to get Voronoi diagrams at higher levels.The results show that a spherical Voronoi di-agram of higher levels can be generated by this algorithm more efficently than those single-level algo-rithms;as it was improved about 22and 25times at Level 9.