ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
392 
Definition 1 (great circle distance on sphere surface) 
If P= {pi, p 2 , .... p in }( 2 <n< °o)is points sets in spherical surface 
S, / and A x are vectors of pieS and p hi €S respectively. The 
shortest distance between points p, and pj is defined as: the 
distance of the shorter arcs in the biggest circle (its center point 
is the center of sphere) via point p and p,. This distance is 
expressed by formula as follow. 
( , )= arccos ( )< n (3.1) 
Definition 2(Voronoi diagram of spherical points sets) 
If P= {pi, p 2 , ..., p n }(2 < n < oo)is points sets in spherical surface 
S, giving a non-empty sets in S. 
() = {|(,)<(, ) * , € , e } (3.2) 
is called Voronoi polygon in sphere about p/. Figure 1 shows a 
spherical voronoi diagram on point sets 
Fig. 1 Spherical Voronoi diagram on point sets 
Definition 3(dilation and erosion based on QTM cells) 
If A is a region in QTM and B is an structure element, the 
operations of dilation and erosion in QTM are as follows (Figure 
2) : 
© = u e 
0 = n e 
A 
B A©B 
A0B 
Fig.2 Dilation and erosion operation in QTM 
4 FINDING METHODS OF SPHERICAL NEIGHBOR 
TRIANGLES 
4.1 Partition method of spherical facet based on QTM 
Originally the concept of spherical facet partition was presented 
by Fuller, a German cartographer, for studying the mapping 
projection in 1940's, after then many researchers have 
approached this problem to analyze and index the global data 
(White, et.at., 1992). Many methods is based on inscribed 
polyhedron (such as tetrahedron, cube, octahedron, 
dodecahedron, icosahedron). Edges of polyhedron are projected 
to the spherical surface and form the edges of spherical triangles. 
This is a basis for global partition. In this paper, we choose an 
octahedron as a basis for an O-QTM, the reason is that it can be 
readily aligned with the conventional geographic grid of longitude 
and latitude. When this is done, its vertices occupy cardinal 
points and its edges assume cardinal directions, following the 
equator, the prime meridian, and the 90 th , 180 ,h and 270 th 
meridians, making it simple to determine which facet a point on 
the planet occupied. Each facet is a right spherical triangle. 
But if recursive partition for the spherical triangle is done, the 
shape and length of triangles have to be varied, i.e. edges and 
internal angles are not equal. There are some methods of 
recursive partition to satisfy the different requires. Latitudes & 
longitudes average method is selected in this paper. When a 
facet is subdivided, the latitudes and longitudes of pairs of its 
vertices are averaged to yield edge midpoint locations, and so on. 
As a result, most of the triangles in the QTM network have 
almost same shapes and area (Figure 3). 
(c) 512 
Fig.3 Hierarchical partition of spherical facet based on octahedron [Dutton, 1996] 
4.2 Code character of QTM 
A point on the earth is usually defined by its longitude X and 
latitude <f>.„ In the QTM triangular hierarchical data structure, the 
position of a point is identified by the centriod of a decomposed 
triangle. The accuracy of estimates of the locations of points 
improves with increasing amounts of decomposition. A QTM 
location address consists of an octant number (from 1 to 8) 
followed by up to 30 quaternary digits (from 1 to 3) which name a 
leaf node in a triangular quadtree rooted in the given octant. At 
the k-th level of decomposition, the triangle address A is 
represented by : A = aoaia 2 a 3 a k . where a r to a k are k 
quaternary digits, while a 0 is an octal digit representing the initial 
Lati. 
Fig.4 (a) Original partition of earth surface; (b) Code in 0 
octant unit