A canonical model of the region connection calculus

ABSTRACT. 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 threedimensional 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 threeand higher-dimensional space this can also be done for internally connected regions. KEYWORDS: qualitative spatial representation, RCC-8, topological relations, spatial regions, modal logic. 1