Spatial reasoning with RCC8RCC8 and connectedness constraints in Euclidean spaces

The language RCC8RCC8 is a widely-studied formalism for describing topological arrangements of spatial regions. The variables of this language range over the collection of non-empty, regular closed sets of n  -dimensional Euclidean space, here denoted RC+(Rn)RC+(Rn), and its non-logical primitives allow us to specify how the interiors, exteriors and boundaries of these sets intersect. The key question is the satisfiability problem  : given a finite set of atomic RCC8RCC8-constraints in m variables, determine whether there exists an m  -tuple of elements of RC+(Rn)RC+(Rn) satisfying them. These problems are known to coincide for all n≥1n≥1, so that RCC8RCC8-satisfiability is independent of dimension. This common satisfiability problem is NLogSpace-complete. Unfortunately, RCC8RCC8 lacks the means to say that a spatial region comprises a ‘single piece’, and the present article investigates what happens when this facility is added. We consider two extensions of RCC8RCC8: RCC8cRCC8c, in which we can state that a region is connected  , and RCC8c∘RCC8c∘, in which we can instead state that a region has a connected interior. The satisfiability problems for both these languages are easily seen to depend on the dimension n  , for n≤3n≤3. Furthermore, in the case of RCC8c∘RCC8c∘, we show that there exist finite sets of constraints that are satisfiable over RC+(R2)RC+(R2), but only by ‘wild’ regions having no possible physical meaning. This prompts us to consider interpretations over the more restrictive domain of non-empty, regular closed, polyhedral   sets, RCP+(Rn)RCP+(Rn). We show that (a) the satisfiability problems for RCC8cRCC8c (equivalently, RCC8c∘RCC8c∘) over RC+(R)RC+(R) and RCP+(R)RCP+(R) are distinct and both NP-complete; (b) the satisfiability problems for RCC8cRCC8c over RC+(R2)RC+(R2) and RCP+(R2)RCP+(R2) are identical and NP-complete; (c) the satisfiability problems for RCC8c∘RCC8c∘ over RC+(R2)RC+(R2) and RCP+(R2)RCP+(R2) are distinct, and the latter is NP-complete. Decidability of the satisfiability problem for RCC8c∘RCC8c∘ over RC+(R2)RC+(R2) is open. For n≥3n≥3, RCC8cRCC8c and RCC8c∘RCC8c∘ are not interestingly different from RCC8RCC8. We finish by answering the following question: given that a set of RCC8cRCC8c- or RCC8c∘RCC8c∘-constraints is satisfiable over RC+(Rn)RC+(Rn) or RCP+(Rn)RCP+(Rn), how complex is the simplest satisfying assignment? In particular, we exhibit, for both languages, a sequence of constraints ΦnΦn, satisfiable over RCP+(R2)RCP+(R2), such that the size of ΦnΦn grows polynomially in n  , while the smallest configuration of polygons satisfying ΦnΦn cuts the plane into a number of pieces that grows exponentially. We further show that, over RC+(R2)RC+(R2), RCC8cRCC8c again requires exponentially large satisfying diagrams, while RCC8c∘RCC8c∘ can force regions in satisfying configurations to have infinitely many components.