6533b7d9fe1ef96bd126ce24

RESEARCH PRODUCT

Spatial reasoning withRCC8and connectedness constraints in Euclidean spaces

subject

description

The language RCC 8 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 + ( R n ) , 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 RCC 8 -constraints in m variables, determine whether there exists an m-tuple of elements of RC + ( R n ) satisfying them. These problems are known to coincide for all n � 1 , so that RCC 8 -satisfiability is independent of dimension. This common satisfiability problem is NLogSpace-complete. Unfortunately, RCC 8 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 RCC 8 : RCC 8 c , in which we can state that a region is connected, and RCC 8 c � , 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 � 3 . Furthermore, in the case of RCC 8 c � , we show that there exist finite sets of constraints that are satisfiable over RC + ( R 2 ) , 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 + ( R n ) . We show that (a) the satisfiability problems for RCC 8 c (equivalently, RCC 8 c � ) over RC + ( R ) and RCP + ( R ) are distinct and both NP-complete; (b) the satisfiability problems for RCC 8 c over RC + ( R 2 ) and RCP + ( R 2 ) are identical and NP-complete; (c) the satisfiability problems for RCC 8 c � over RC + ( R 2 ) and RCP + ( R 2 ) are distinct, and the latter is NP-complete. Decidability of the satisfiability problem for RCC 8 c � over RC + ( R 2 ) is open. For n � 3 , RCC 8 c and RCC 8 c � are not interestingly different from RCC 8 . We finish by answering the following question: given that a set of RCC 8 c - or RCC 8 c � -constraints is satisfiable over RC + ( R n ) or RCP + ( R n ) , how complex is the simplest satisfying assignment? In particular, we exhibit, for both languages, a sequence of constraints � n , satisfiable over RCP + ( R 2 ) , such that the size of � n grows polynomially in n, while the smallest configuration of polygons satisfying � n cuts the plane into a number of pieces that grows exponentially. We further show that, over RC + ( R 2 ) , RCC 8 c again requires exponentially large satisfying diagrams, while RCC 8 c � can force regions in satisfying configurations to have infinitely many components.