Topological Relations Between Regions in R2 and Z2

Max Egenhofer and Jayant Sharma
Advances in Spatial Databases--Third International Symposium on Large Spatial Databases, SSD `93, Singapore, D. Abel and B.C. Ooi (eds.), Lecture Notes in Computer Science, Vol. 692, Springer-Verlag, pp. 316-336, June 1993.

Abstract

Users of geographic databases that integrate spatial data represented in vector and raster models, should not perceive the differences among the data models in which data are represented, nor should they be forced to apply different concepts depending on the model in which spatial data are represented. A crucial aspect of spatial query languages for such integrated systems is the need mechanisms to process queries about spatial relations in a consistent fashion. This paper compares topological relations between spatial objects represented in a continuous (vector) space of R2 and a discrete (raster) space of Z2. It applies the 9-intersection, a frequently used formalism for topological spatial relations between objects represented in a vector data model, to describe topological relations for bounded objects represented in a raster data model. We found that the set of all possible topological relations between regions in R2 is a subset of the topological relations that can be realized between two bounded, extended objects in Z2. At a theoretical level, the results contribute toward a better understanding of the differences in the topology of continuous and discrete space. The particular lesson learnt here is that topology in R2 is based on coincidence, whereas in Z2 it is based on coincidence and neighborhood. The relevant differences between the raster and the vector model are that an object's boundary in Z2 has an extent, while it has none in R2; and in the finite space of Z2 there are points between which one cannot insert another one, while in the infinite space of R2 between any two points there exists another one.

PDF