ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
173 
a spatial relation cannot be sufficiently described even 
dimension is used. In this case, connected number should also 
be considered. 
4. VORONOI-BASED SPATIAL ALGEBRA FOR SPATIAL 
RELATIONS: FURTHER EXTENSION 
In the previous section, a simple spatial algebra is developed 
for spatial relations. However, as will be discussed later, some 
spatial relations will be confused if only the spatial objects are 
used. In order to make the spatial algebra more general, 
Voronoi regions of spatial objects are introduced into this model 
expressed in Equation (1). 
4.1 Voronoi region as a topological component of a 
spatial object 
Spatial relations essentially reflect the spatial configuration 
between objects. In other words, for individual object, the 
surrounding space must also be taken into account in addition 
to the surrounding objects if sound models for spatial relations 
are to be developed. The role of Voronoi region in this study 
serves the purpose of tightening the inter-relation among a 
spatial object and its neighbouring objects and space. 
A Voronoi region describes the spatial proximity or influent 
region of a spatial object. The Voronoi regions of all spatial 
objects together will form a tessellation of space. This 
tessellation is called Voronoi diagram. There are also other 
names but such discussion and other topics could be found 
elsewhere (Li et al. 1999). The dual graph is the well-known 
Delaunnay triangulation network in GIS and computational 
geometry. Figure 2 illustrates Voronoi regions, Voronoi 
diagram and the corresponding Delaunnay triangulation of a 
point set. Figure 4 shows Voronoi regions of two objects with 
two different kinds of spatial configurations. 
(a) (b) 
Figure 4: Voronoi regions of spatial objects with complex 
configurations 
It is clear that the Voronoi region of a spatial object could serve 
for two purposes, i.e. to connect spatial objects together to form 
a space tessellation and, at the same time, to serve as a 
confined exterior of the spatial object. Therefore, Voronoi 
region is introduced into the spatial algebra for spatial relations. 
As a result, a Voronoi-based spatial algebra is presented for 
general use. 
4.2 Voronoi-based spatial algebra: further extension 
Let a v be the Voronoi region of spatial object 'a' and b v be the 
Voronoi region of spatial object 'b\ then the spatial relation B(a, 
b) between object a and object b can be listed in Table 1 
concisely, which can be expanded to be a matrix form as in 
Table 2: 
Table 1: Concise representation of the new algebraic model 
B(a,b)=F{A T 0 B) 
b 
b v 
a 
(a 6b) 
(a 1 6b v ) 
a v 
(a v 6 b) 
(a 1 Ob') 
Table 2: The extended form of the algebraic model based 
on Voronoi regions 
B(a,b)- F(A T 0 B) 
(a. b) 
(a. h v ) 
(a 1 : h) 
(a . h y ) 
Union ci 
au b 
au b 1 
a' ub r 
a' u b' 
Intersect n 
ar\b 
a r> A 1 
a v r\h' 
ä 1 n h' 
Difference \ 
a \ h 
a ’ h { 
a' h 1 
a' \ h‘ 
Difference by / 
alb 
alb' 
a v lb v 
a'/h' 
Symmetric difference A 
a Ab 
a A h' 
a' A b' 
a' Ah' 
Other operators 
Mathematically, let A = [a, a 1 '] and B = [b, b v ], then the relations 
could be described by the following equation: 
B(a,b ) = F(A r 0B) = F{[a, a v } r 0[b ,b v ]) 
(a 0b) {adb v )\ 
(„'№> (S»«')J 
Where, F is function similar to the fin Equation (1). Generally 
speaking, the following function is sufficient: 
B\a,b)= F {( a Ob), (a y Ob y )} (3a) 
In practice, if a spatial relation can be sufficiently described by 
(aOb), the other operand, i.e. (a 0 b v ), may be ignored. 
Of course, one may also try to use the (a 1 Ob 1 ) first if he 
wishes. As a result, in this way, spatial relations can be 
described in a flexible manner. 
5. TOPOLOGICAL RELATIONS WITH THE SPATIAL 
ALGEBRA 
In the previous section, the basic algebraic model has been 
presented. In this section, the realization of this model in 
real-world relations will be presented. 
5.1 Assumptions used in the model 
In fact, not all the values of the Equation (3) and/or Table 2 are 
valid in practical applications. A number of assumptions could 
be made for the determination the useful values of the Equation 
(3) and Tables 1 and 2. These assumptions are formulated by 
considering a number of factors, i.e. the properties of spatial 
objects, the embedding space, the relations between selected 
operators in the model and so on. These assumptions are