ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
395 
From figure 9, we can see that distance distortion of QTM cells 
dilations is not only related to distance, but also related to 
location. The distortions change differently by dilation increasing 
when the origin objects in different location. 
• Distance distortion between great circle distance and QTM 
cells distance change little when the object is located at or 
near corner triangles (as points 2, 3 and 4 in Fig.9); 
• Distance distortion is an almost linear function of distance 
r 
( 1 ) raster in planar ( 2 ) left-corner triangle 
itself when the object is located at or near triangles in 
midpoint of edges (as points 5, 6 and 7). 
• If the objects are located in or near the center of the octant 
triangle, the distortion increases when the distance 
increases. But when the dilation covers half globe, 
distortion decreases when the distance increases, and 
reduces to zero at in the end (as points 8 in Fig.9). 
( 3 ) right corner triangle 
( 4 ) top comer triangle 
Fig.9 Distance distortion of QTM cells dilations in different location 
7 CONCLUSIONS 
Voronoi diagram data structure becomes an efficient tool to 
solve global GIS dynamic data model by its dynamic stability. 
Hierarchical expression of spherical QTM presents a method 
of data generalization to deal with large quantity of data. In this 
paper, Voronoi generating algorithms is presented by recursive 
dilation of spherical objects and calculated program is 
developed in platform OpenGL with VC +t language. An 
analysis of experiment results and errors are made, and 
conclusion are as followings: 
1) QTM-based method for generating Voronoi diagram of 
spherical objects has simple concepts and easily 
extent. Voronoi diagram for arcs and area sets can 
also be constructed as easily as for point sets. 
2) Data of spherical objects expressed by QTM address 
code have hierarchical quadtree structure, and suitable 
to solve the problem of multi-hierarchical 
generalization of large quantity of spherical data. 
3) Consume of time and space of algorithms is direct 
proportion to partition levels, and the quantity of data 
can be controlled by the size of pixel. Error of 
generating Voronoi diagram is related to location of 
sets, and has no relation to the distances. 
8 ACKNOWLEDGEMENTS 
The National Science Foundation of China under grant No. 
69833010 supported this research. 
REFERENCES 
Augenbaum, M.& Pesken C., 1985, On the Construction of the 
Voronoi Mesh on a Sphere. Computational Physics Vol 59. 
PP177-192. 
Aurenhammer, F., 1991, Voronoi Diagram-A Survey of a 
Fundamental Geometric Data Structure, ACM Computing 
Survey, Vol.23(3), pp345-350 
Dutton, G., 1996, Encoding and Handling Geospatial Data with 
Hierarchical Triangular Meshes, Proceeding of 7th 
International Symposium on Spatial Data Handling. 
pp34-43 
Dutton, G.,1999, Scale, Sinuosity, and Point Selection in Digital 
Line Generalization, Cartography and Geographic 
Information Science, Vol. 26, No.1, pp33-53 
Gold C.M, 1997, the Global GIS, Proceeding of the 
International Workshop on Dynamic and Multi-Dimension 
GIS, Hong-Kong, China, pp80-91 
Goodchild, M.F., and Yang Shiren, 1992. A hierarchical data 
structure for global geographic information systems. 
CVGIP, 54:1, pp.31-44. 
Goodchild, M.F., Yang Shiren and GDutton, 1991. Spatial Data 
Representation and Basic Operations for A Triangular 
Hierarchical Data Structure, NCGIA report, 91-8. 
Lukatela.H, 1987, Hipparchus Geopositioning Model: An 
Overview. Proceedings of the Eighth International 
Symposium on Computer-Assisted Cartography, pp. 87-96 
Lukatela.H,1989 Hipparchus Data Structure: Points,Lines 
and Regions in Spherical Voronoi Grid. Proceedings of the 
Ninth International Symposium on Computer-Assisted 
Cartography, pp. 164-170 
Okabe.A., Boots,B., and Sugihara.K., 1992, Spatial 
Tessellations Concepts and Applications of Voronoi 
Diagrams, pp192-194, 269-271 
Robert J.R., 1997, Delaunay Triangulation and Voronoi 
Diagram on the Surface of a Sphere, ACM Transactions 
on Mathematical Software, Vol.23, No.3, September, 
pp416-434.. 
Yang W. C.Gold, 1996, Managing Spatial Objects With the 
VMO-Tree, Proceeding of 7th International Symposium on 
Spatial Data Handling, Netherlands, pp15-31 
Watson, D.F., 1988, Natural neighbor sorting on the 
n-dimensional sphere, Pattern Recognition, 21(1), 63-67 
Wright, D. & Goodchild, M.F., 1997, Data from Deep: 
Impliications for the GIS Community, INT.J. Geographical 
Information Science, Vol. 11, No. 6, pp523-528 
White, D., Kimmerling.J., and Overton,W.S., 1992, 
Cartographic And Geometric Components of a Global 
Sampling Design For Environment Monitoring. CaGIS, 
19:1, pp. 5-22.