Voronoi tessellation defines only the ‘influence area’ of the spatial objects could 
not describe and represent the spatial objects. So we want to develop the 
integrated data model of graph based spatial data model with the Voronoi approach 
in discrete space. The idea is to divide the discrete space under consideration 
into Voronoi tessellation according to spatial point, line and polygon objects, and 
integrate the planar graph-based model and the Voronoi tessellation into a new data 
model and the Voronoi tessellation into a new data model, i.e, planar graph-based 
Voronoi spatial data model. 
Computational geometry is concerned with the design and analysis of algorithms 
for geometrialproblems. In addition, other more practically oriented, areas of 
computer science, computer-aided design, robotics, pattern recognition, and 
operations research -give rise to problems that inherently are geometrícal.. In few 
years, an increasing interest in a geometrical construct called the Voronoi Diagram. 
Given some number of points in the plane, their Voronoi Diagram divides the plane 
according to the nearest -neighbor rule: Each point is associated with the region 
of the plane closet to it 
2. Voronoi Diagram in discrete space. 
The Raster Voronoi Diagram is defined as one kind of Voronoi Diagram generated in 
discrete space. Although it is the same in nature as vector Voronoi Diagram, the 
algorithms of generating 2D and 3D raster raster Voronoi Diasram is different 
compared with that in vector space. 
2.1 The definition of spatial objects. 
In the discrete space the point objects are defined as in the follows: 
(1). A={four points around the center objects} 
(2), A={only one point} 
The boundary and interior define the line-like objects as the strictly 4-neighbor 
or 8-neighbor. 
(1). A={strictly 4-neighbcr cr $-neighbor.! 
(2). A={strictly 4-neighbor or 8-neighbor. } 
The boundary and interior also define the area-like objects as the strictly 4- 
neishbor or $8-neishbor. 
(1). A={not strictly 4-neighbor or 8-neighbor. } 
(2. A={nct strictly 4-neighbor cr 8-neighbor.] 
2.2 Voronoi Diagram in discrete space. 
For a boundary 2D space, there exists a subsets of hybrid spatial objects as 
fotiewsPeip.p D I Pi 15 -coHed 01 genoratcr. For P4," P: 
Hpipi={X: LIX-Pi | |«e | IX-P jl D. Kpipje X: HIX-Pi L lS IX-P jl E 
Hpipj is half plane. Kpipj is boundary. Rp=NHpq {g=p}, R={Rp lp P},Ris called the 
Voronoi Diagram of the spatial objects. 
in the discrete space the definition of distance is most important in generating 
raster Vorcnoi diagram. The distance of spatial objects is defined as: 
228 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996