

![0_image_0.png](0_image_0.png) 

The Region Conne tion Cal ulus RCC-8 is a onstraint language formed by the eight jointly exhaustive and pairwise disjoint base relations DC, EC, PO, EQ, TPP, NTPP, TPP1, and NTPP1 denable in the RCC-theory and by all possible unions of the base relations| giving a total number of 28 = 256 dierent relations. The base relations have the meaning of DisConne ted, External ly Conne ted, Partial Overlap, EQual, Tangential Proper Part, Non-Tangential Proper Part, and their onverses. Examples for these relations are shown in Figure 1. Constraints are written in the form xRy where x; y are variables for spatial regions and R is an RCC-8 relation. We write the union of base relations as fR; Sg. The union of all base relations, the universal relation, is written as fg. Apart from union

([), other operations on relations are dened, namely, onverse (^), interse tion (\), and omposition (Æ). The formal denitions of these operations are:

$$\begin{array}{l l l l}{{\forall x,\,y:}}&{{x(R\cup S)y}}&{{\leftrightarrow}}&{{x R y\,\vee x S y,}}\\ {{\forall x,\,y:}}&{{x(R\cap S)y}}&{{\leftrightarrow}}&{{x R y\wedge x S y,}}\\ {{\forall x,\,y:}}&{{x R^{-}y}}&{{\leftrightarrow}}&{{y R x,}}\\ {{\forall x,\,y:}}&{{x(R\circ S)y}}&{{\leftrightarrow}}&{{\exists z\,:(x R z\,\wedge z S y).}}\end{array}$$

The omposition of base relations an be omputed from the semanti s of the relations and is usually provided as a omposition table (Randell, Cohn, & Cui, 1992a; Bennett, 1994). The RCC-8 omposition table orresponds to the given extensional denition of omposition only if the universal region is not permitted (Bennett, 1997). Based on this table, ompositions of disjun tive relations an be easily omputed. In the following, Sb denotes the losure of a set of RCC-8 relations S under omposition, interse tion, and onverse.

A nite set of RCC-8 onstraints - des ribing the topologi al relationships of n dierent regions an be represented by an nn matrix M, where ea h entry Mij represents the RCC-8 relation holding between region i and region j. Without loss of generality, Mii = fEQg and Mj i = M^
ij 
an be assumed. The fundamental reasoning problem (named RSAT) in this framework is de iding onsisten y of a set of spatial formulas , i.e., whether there is a spatial onguration where the relations between the regions an be des ribed by . All other interesting reasoning problem an be redu ed to it in polynomial time (Golumbi 
& Shamir, 1993). Unfortunately, RSAT is NP-
omplete (Renz & Nebel, 1999), i.e., it is unlikely that there is any polynomial algorithm for de iding onsisten y. However, it was shown in Nebel's (1995) paper that there are subsets S of RCC-8 for whi h the onsisten y
