ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
170 
AN ALGEBRA FOR SPATIAL RELATIONS 
Zhilin LI \ Renliang ZHAO 1,2 and Jun CHEN 2 
1 Department of Land Surveying and Geo-Informatics 
The Hong Kong Polytechnic University, Kowloon, Hong Kong, China 
lsllz@polyu.edu.hk 
2 National Geometries Center of China, 
1 Baishengcun, Zizhuyuan, Beijing, China, 10004 
KEYWORDS: Spatial algebra, spatial relation, topological relation, set operation, Voronoi region, Voronoi diagram 
ABSTRACT 
Spatial relation is a very important topic for spatial reasoning, query and analysis in GIS. This paper presents a generic algebra for 
spatial relations. In this algebra, (a) appropriate operators from set operators (i.e. union, intersection, difference, difference by, 
symmetric difference, etc) are utilised to distinguish the spatial relations between neighbouring spatial objects; (b) three types of values 
are used for the computational results of set operations, -- content, dimension and number of connected components; (c) a spatial 
object is treated in a whole but the Voronoi region of an object is employed to enhance its interaction with neighbours; This is a more 
generic model than existing ones in theory and practice. This approach overcomes the shortcomings of both decomposition-based and 
whole-based approaches. The models developed in this project form an algebra which can effectively describes the relations of spatial 
objects. From practical viewpoint, using this approach, the integration of the description and computation of spatial relations in both 
vector and raster space is realised in a natural way. 
1. INTRODUCTION 
A formal theory of description and determination for relations 
between spatial objects is usually important to spatial query, 
analysis and reasoning in GIS field. For example, in the case 
of digital map generalisation, spatial relations between map 
objects will be altered after applying generalisation operations 
such as selective omission, aggregation, displacement, 
exaggeration and so on. These relations could be metric 
and/or topological. Due to such changes, spatial conflicts may 
be created by these operations and such conflicts need to be 
checked and resolved. Recently, much attention has been paid 
to this topic (e.g. Dettori and Puppo, 1996). For such a purpose, 
appropriate mathematical models for spatial relations are 
required. 
The importance of spatial relation theory has already been 
recognised in early 1980s (Marble 1984, Abler 1987). Since 
then, many papers on this topic have been published by 
researchers from computing science and GIS communities. 
The approaches used in these works can be classified into two 
categories, i.e. decomposition-based and whole-based 
(Abdelmoty et al. 1994). In the former, a spatial object is 
represented in terms of the set of its components, and, 
relations are described and determined by the combinatorial 
relations of those components. In the latter, the spatial object is 
considered as a whole and, spatial relations between spatial 
objects are described and determined by the interaction 
between whole bodies of these objects instead of their 
components. 
In the category of decomposition-based approaches, most 
models are built upon point set topology (Guting 1988, Pullar 
1988, Egenhofer 1989, Clementini et al. 1993). In these 
models, two or three components of a spatial object, i.e. interior, 
boundary and exterior, are utilised. The most fundamental one 
is the 4-intersection model by Egenhofer and Franzona (1991), 
making use of the interior and boundary of a spatial object. 
Later, this model has been extended to 9-intersection model 
(Egenhofer and Herring 1991), in which the exterior of a spatial 
object is also included. These models have been implemented 
in raster mode by Winter and his collaborators (Winter 1995, 
Winter and Frank 2000), through the use of vector 
representation for raster cells. The 9-intersection model is then 
modified by Chen et al. (2001) by replacing the complement of 
a spatial object with its Voronoi region. 
In the category of whole-based approach, main work includes 
the spatial logic model developed by Randell et al. (1992) and 
temporal logic model by Allen (1983). The former is built upon 
the calculus of individuals (Clarke 1981) which is in turn based 
on “region connection" ontology. In this model, a set of 
topological relationships between concave regions is 
axlomatised. Some other work based on Clarke's region 
theory can also been found in literature (e.g. Vieu 1993). The 
main advantage of such work rests in its rigorous logic so as to 
facilitate the mathematical deduction and proof. Such models 
have mainly been applied to objects of regions in the context of 
artificial intelligence. Allen's temporal logic relations (Allen 
1983) was originally put forward to handle two-dimensional 
temporal but later it has been widely extended to higher 
dimensional space (e.g. Freksa 1991, 1992; Hernandez 1993, 
1994). Unfortunately, most of these models are limited to the 
point-based abstraction of spatial objects. 
In spite of these efforts and progresses in the last decade, it is 
not deniable that there are many imperfections associated with 
existing work as will be discussed in Section 2. In other words, 
the formal description and determination of spatial relations is 
still an open issue and it deserves further research (e.g. Vasilis 
et al. 1999). In this paper, an alternative approach is proposed, 
i.e. an algebraic approach based on Voronoi regions. This is 
indeed a whole-based approach. In order to capture the