We define a finite relation algebra and show that the network satisfaction problem is undecidable for this algebra.

Although the computational properties of the Region Connection Calculus RCC-8 are well studied, reasoning with RCC-8 entails several representational problems. This includes the problem of representing arbitrary spatial regions in a computational framework, leading to the problem of generating a realization of a consistent set of RCC-8 constraints. A further problem is that RCC-8 performs reasoning about topological space, which does not have a particular dimension. Most applications of spatial reasoning, however, deal with two- or three-dimensional space. Therefore, a consistent (...) set of RCC-8 constraints might not be realizable within the desired dimension. In this paper we address these problems and develop a canonical model of RCC-8 which allows a simple representation of regions with respect to a set of RCC-8 constraints, and, further, enables us to generate realizations in any dimension d = 1. For three-and higher-dimensional space this can also be done for internally connected regions. (shrink)