An algorithm for the generation of Voronoi diagrams on the sphere based on QTM

Jun Chen, Xuesheng Zhao, Zhilin Li

Research output: Journal article publicationReview articleAcademic researchpeer-review

45 Citations (Scopus)


In order to efficiently store and analyze spatial data on a global scale, the digital expression of Earth data in a data model must be global, continuous, and conjugate, i.e., a spherical dynamic data model is needed. The Voronoi data structure is the only published attempt (Wright and Goodchild, 1997) and the only possible solution currently available (Li et al., 1999) for a dynamic GIS. However, the complexity of the Voronoi algorithm for line sets and area sets in vector mode limits its application in a dynamic GIS. So far, there is no raster-based Voronoi algorithm for objects (including points, arcs, and regions) on a spherical surface. To overcome this serious deficiency, an algorithm for generating a spherical Voronoi diagram is presented, based on the O-QTM (Octahedral Quaternary Triangular Mesh). The principle of the dilation operation in mathematical morphology is extended to the spherical surface. A method is developed for a spherical distance transformation based on the QTM. A detailed algorithm is also presented. This algorithm can handle points, arcs, and area features on a spherical surface. Tests have shown that the computational time consumption of this algorithm with points, arcs, and areas is equal and proportionate to the levels of the spherical surface tessellation; and the difference (distortion) between the great circle distance and the QTM cells distance is slightly related to spherical distance (not as the raster dilation on a planar surface), and is mainly related to the locations of the generating points.
Original languageEnglish
Pages (from-to)79-89
Number of pages11
JournalPhotogrammetric Engineering and Remote Sensing
Issue number1
Publication statusPublished - 1 Jan 2003

ASJC Scopus subject areas

  • Computers in Earth Sciences


Dive into the research topics of 'An algorithm for the generation of Voronoi diagrams on the sphere based on QTM'. Together they form a unique fingerprint.

Cite this