Institut für Informatik

Technical Report No. 96, July 1996 - Abstract

Renz, J.:
A Canonical Model of the Region Connection Calculus

Canonical models are very useful for determining simple representation formalism for qualitative relations. Allen's interval relations, e.g., can thereby be represented using the start and the end point of the intervals. Such a simple representation was not possible for regions of higher dimension as used by the Region Connection Calculus. In this paper we present a canonical model which allows regions and relations between them to be represented as points of the topological space and information about their neighbourhoods. With this formalism we are able to prove that whenever a set of RCC-8 formulas is consistent there exists a realization in any dimension, even when the regions are constrained to be (sets of) polytopes. For three- and higher dimensional space this is also true for internally connected regions. Using the canonical model we give algorithms for generating consistent scenarios.

Report No.96 (PostScript)