Abstract:

Voronoi diagram is a very useful tool for spatial analysis of many geographical problems. However, we now still lack a simple approach or a software to construct Voronoi diagram with general generators (such as curves and areas), and so this paper presents a GIS-based Approximation Algorithms for Constructing Voronoi Diagrams with general generators. We first replace each generators with a finite number of points that approximate the original generators, then the Voronoi diagrams for these points are constructed, and superfluous Voronoi edges and superfluous Voronoi vertices are finally removed. Thus we can get the approximation of Voronoi diagram with original generators. In practical implementation, we fully employed the module of ARCGIS software with a fast and robust algorithm to construct the ordinary Voronoi diagrams, and also some other modules of it. The result of experiment shows that it is an efficient and effective method for constructing Voronoi diagram with generators of any form figures, and it is a promising approach for the need of geographical research issues. For example, Voronoi diagrams by this approach can be represented as he spatial effect area for a variety of geographical objects with the different forms, such as points (cities, towns, transport junctions, trade centers), and lines (transport lines, industrial belts, river system), and areas (economic regions, parks and green lands), and so forth.

Key words: approximation algorithm, geographical information systems, Voronoi diagram