ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS’’, Bangkok, May 23-25, 2001 
391 
QTM-BASED ALGORITHM FOR THE GENERATING OF VORONOI DIAGRAM FOR SPHERICAL OBJECTS 
Xuesheng ZHAO 1 Jun CHEN 2 
1 China University of Mining and Technology (Beijing) 
D11 Xueyuan Road, Beijing, China, 100083 
E-mail, zxs@mail.cumtb.edu.cn 
National Geomatics Center of China 
No1. Zizhuyuan, Baishengcun, Beijing, China, 100044 
E-mail: ¡chen@gps.ceic.aov.cn 
KEY WORDS: Spherical dynamic data model QTM Voronoi diagram Recursive dilation 
ABSTRACT 
This paper present an algorithm for generating of spherical Voronoi diagram based on O-QTM (Octahedral Quaternary Triangular Mesh). 
First the methods of spherical surface triangular partition and encode of triangular are reviewed. With the codes of triangular, the direct 
and non-direct neighbor triangular can be searched. In this paper, the dilation operator and dilation-structuring element of spherical 
triangular are redefined according to the principle of mathematical morphology. So the spherical Voronoi diagram is generated by 
recursive dilation of spherical objects expressed by code of triangular. We developed the experimental system using VC++ in OpenGL 
platform and analysis the complex degree of algorithm and features of errors. The results demonstrated: the complex degree of 
algorithm with points, arcs and curve faces are equal, and proportion to levels of the spherical face partition; and the error of result is 
related a little to spherical distance, not as the raster dilation in planar, and is related mainly to the locations of the objects. In the end, 
the conclusions and future works are presented. 
1 INTRODUCTION 
The classical data model cannot manage the global, changed, 
and large quantity of data effectively because it is based on 
planar and static. In order to effectively store, pick up and 
analysis the spatial data in global scale, the digital expression of 
the Earth data in computer must be global, continuous and 
conjugate, i.e., construct the spherical dynamic data model. As 
Voronoi data structure is one of the moat value tools in dynamic 
operation by its characters [White et al, 1997]. But the complex 
of the Voronoi algorithm limits its application in GIS. There are 
few Voronoi algorithms in sphere, only in spherical points sets, 
and can not satisfy the requirement of dynamic operation of 
spherical data. 
So algorithms based on raster starts to be approached. Voronoi 
algorithms have simple conception and recursive and can control 
quantity and precision by pixels. Now from the papers, Voronoi 
algorithms based on raster are only limited on planar and can not 
extend these methods to spherical surface because planar and 
spherical facet are not homoeomorphism. In this paper spherical 
surface is partitioned by QTM. Dilation operator and structure 
element are redefined according to the principle of mathematical 
morphology. Voronoi generating algorithms is presented by 
recursive dilation of spherical objects and calculated program is 
developed in platform OpenGL with VC ++ language. 
Following this introduction is section for background review and 
analyzing the advantages and disadvantages of vector-based 
methods. Section 3 will introduce some basic concepts related to 
Voronoi diagram of spherical objects. Section 4 will discuss 
partition method of spherical surface and character of QTM code, 
and present finding methods of spherical neighbor triangles in 
details. In section 5, an algorithm for generating Voronoi of 
spherical objects is presented in details by dilation principle of 
QTM. An analysis of experiment results and errors are made, 
and error control method is presented in section 6. At last, the 
conclusions and future works will be presented. 
2 METHODS FOR SPHERICAL VORONOI DIAGRAM 
GENERATION: A REVIEW AND OVERVIEW 
Voronoi diagram has been one of the research hotspots in area 
of computer geometry since it is introduced to computer area by 
Shamos & Hoey[1975] as an efficient data structure. Most of 
methods are based on point sets in planar, such as incremental 
method, divide and conquer, indirect generating method and 
parallel method [Aurenhammer, 1991]. 
There are a few methods based on spherical surface. Such as, 
Aggenbaum et al. [1985] give an 0(m 2 ) time insertion method for 
computing the Voronoi diagram of a set of m points on a sphere. 
Renky [1997] give an O(NlogN) time to construct the Delaunay 
triangular, the dual of the Voronoi diagram of a set of n points on 
a sphere. Lukatela [1987,1989] set up a digital geo-positioning 
model and develop an operational software package that 
provides geometrical & geo-relational functions to applications 
that manipulate spatial objects. A Voronoi tessellation is used as 
a base for highly efficient indexing system to increase the speed 
of data manipulation. It is a first application system based on 
sphere surface model in GIS. It is same as Walson [1988] who 
use point-sets Voronoi diagram to interpolation on spherical 
surface. From above, we can see that Voronoi diagram is 
constructed for only point sets on sphere and based on vector 
mode. It has been realized [Gold, 1992] that vector-based 
methods are good only for point sets and the methods for line 
and area sets could be very complex. Especially the arc and area 
sets in 3-D and spherical surface are really out of consideration. 
That serious deficiency is main obstacle to use widely in GIS 
applications. In order to solve this problem, Yang & Gold [1996] 
presented a point-line model, i.e. the complex objects are 
decomposed to points and lines. Voronoi diagram for points and 
lines are generated at first, and then translate to Voronoi diagram 
of the complex objects by removing the Voronoi edges between 
points or line in a same object. The advantage of this methods 
can generate Voronoi diagram of the complex vector-based 
objects and deal with dynamic changes of topological relations. 
But it has been done by many steps, such as 
“decompose”, "calculation”, ’’remove" and “compose". Algorithms 
and data structure are complex, especially lack of hierarchical 
data structure, and cannot deal with hierarchical generalized 
expression of quantity of spherical data. 
As the complex of vector-based methods, raster-based methods 
have been approached. Li Chengming et.al [1999] presented a 
method based on raster by dynamic distance translation with 
principle of mathematical morphology and restrict the error to 
one pixel. Raster-based methods have simple conception, 
hierarchical recursive, and easily extended to 3-D Voronoi 
diagram. But now the research limited in planar. So far, the 
authors, in a real sense have known no literature purely on the 
generation of Voronoi diagram in spherical mesh-based 
methods. 
3 RELATED CONCEPTS & DEFINITIONS 
The followings are related concepts and definitions.