On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

1 Introduction

A central task in Qualitative Spatial Reasoning is that of determining whether some described spatial configuration is geometrically realizable in 2D or 3D Euclidean space. Typically, such a description is given using a spatial logic-a formal language whose variables range over (typed) geometrical entities, and whose non-logical primitives represent geometrical relations and operations involving those entities. Where the geometrical primitives of the language are purely topological in character, we speak of a topological logic; and where the logical syntax is confined to that of propositional calculus, we speak of a topological constraint language.

Topological constraint languages have been intensively studied in Artificial Intelligence over the last two decades. The best-known of these, RCC8 and RCC5, employ variables ranging over regular closed sets in topological spaces, and a collection of eight (respectively, five) binary predicates standing for some basic topological relations between these sets [Egenhofer and Franzosa, 1991; Randell et al., 1992; Bennett, 1994; Renz and Nebel, 2001]. An important extension of RCC8, known as BRCC8, additionally features standard Boolean operations on regular closed sets [Wolter and Zakharyaschev, 2000].

A remarkable characteristic of these languages is their insensitivity to the underlying interpretation. To show that an RCC8-formula is satisfiable in n-dimensional Euclidean space, it suffices to demonstrate its satisfiability in any topological space [Renz, 1998]; for BRCC8-formulas, satisfiability in any connected space is enough. This inexpressiveness

2School of Computer Science University of Manchester, U.K.

yields (relatively) low computational complexity: satisfiability of BRCC8-, RCC8- and RCC5-formulas over arbitrary topological spaces is NP-complete; satisfiability of BRCC8formulas over connected spaces is PSPACE-complete.

However, satisfiability of spatial constraints by arbitrary regular closed sets by no means guarantees realizability by practically meaningful geometrical objects, where connectedness of regions is typically a minimal requirement [Borgo et al., 1996; Cohn and Renz, 2008]. (A connected region is one which consists of a 'single piece.') It is easy to write constraints in RCC8 that are satisfiable by connected regular closed sets over arbitrary topological spaces but not over R2 ; in BRCC8 we can even write formulas satisfiable by connected regular closed sets over arbitrary spaces but not over Rn for any n. Worse still: there exist simple collections of spatial constraints (involving connectedness) that are satisfiable in the Euclidean plane, but only by 'pathological' sets that cannot plausibly represent the regions occupied by physical objects [Pratt-Hartmann, 2007]. Unfortunately, little is known about the complexity of topological constraint satisfaction by non-pathological objects in low-dimensional Euclidean spaces. One landmark result [Schaefer et al., 2003] in this area shows that satisfiability of RCC8-formulas by disc homeomorphs in R2 is still NP-complete (even though formulas can force arrangements that cut the plane into exponentially many regions). This paper investigates the computational properties of more general and flexible spatial logics with connectedness constraints interpreted over R2 and R3 .

We consider two 'base' topological constraint languages. The language B features = as its only predicate, but has function symbols +, -, · denoting the standard operations of fusion, complement and taking common parts defined for regular closed sets, as well as the constants 1 and 0 for the entire space and the empty set. Our second base language, C, additionally features a binary predicate, C, denoting the 'contact' relation (two sets are in contact if they share at least one point). The language C is a notational variant of BRCC8 (and thus an extension of RCC8), while B is the analogous extension of RCC5. We add to B and C one of two new unary predicates: c, representing the property of connectedness, and c◦ , representing the (stronger) property of having a connected interior. We denote the resulting languages by Bc, Bc◦, Cc and Cc◦. We are interested in interpretations over (i) the regular closed sets of R2 and R3 , and (ii) the regular closed polyhedra in R2 and R3 . (A set is polyhedral if it can be defined by finitely many bounding hyperplanes; see Sec. 2.) By restricting interpretations to polyhedra, we rule out pathological sets, and, in effect, use the same 'data structure' as in GISs.

When interpreted over arbitrary topological spaces, the complexity of reasoning with these languages is known: satisfiability of Bc◦ -formulas is NP-complete, while for the other three languages, it is EXPTIME-complete. Likewise, the 1D Euclidean case is completely solved. For the spaces Rn (n ≥ 2), however, most problems are still open. All four languages contain formulas satisfiable by regular closed sets in R2 , but not by regular closed polygons; in R3 , the analogous result is known only for Bc◦ and Cc◦ . The satisfiability problem for Bc, Cc and Cc◦ is EXPTIME-hard (in both polyhedral and unrestricted cases) for Rn (n ≥ 2); however, the only known upper bound is that satisfiability of Bc◦ - formulas by polyhedra in Rn (n ≥ 3) is EXPTIME-complete. (See [Kontchakov et al., 2010b] for a summary.)

This paper settles most of these open problems, revealing considerable differences between the computational properties of constraint languages with connectedness predicates when interpreted over R2 and over abstract topological spaces. Sec. 3 shows that Bc, Bc◦ , Cc and Cc◦ are all sensitive to restriction to polyhedra in Rn (n ≥ 2). Sec. 4 establishes an unexpected result: all these languages are undecidable in R2 , both in the polyhedral and unrestricted cases ([Dornheim, 1998] proves undecidability of the first-order versions of these languages). Sec. 5 resolves the open issue of the complexity of Bc◦ over regular closed sets (not just polyhedra) in R3 by establishing an NP upper bound. Thus, Qualitative Spatial Reasoning in Euclidean spaces proves much more challenging if connectedness of regions is to be taken into account. We discuss the obtained results in the context of spatial reasoning in Sec. 6. Omitted proofs can be found in [Kontchakov et al., 2011].

2 Constraint Languages with Connectedness

Let T be a topological space. We denote the closure of any X ⊆ T by X- , its interior by X◦ and its boundary by δX = X- \X◦ . We call X regular closed if X = X◦- , and denote by RC(T) the set of regular closed subsets of T. Where T is clear from context, we refer to elements of RC(T ) as regions. RC(T) forms a Boolean algebra under the operations X + Y = X ∪ Y , X · Y = (X ∩ Y )◦- and -X = (T \X)- . We write X ≤ Y for X · (-Y ) = ∅; thus X ≤ Y iff X ⊆ Y . A subset X ⊆ T is connected if it cannot be decomposed into two disjoint, non-empty sets closed in the subspace topology; X is interior-connected if X◦ is connected.

Any (n-1)-dimensional hyperplane in Rn , n ≥ 1, bounds two elements of RC(Rn ) called half-spaces. We denote by RCP(Rn ) the Boolean subalgebra of RC(Rn ) generated by the half-spaces, and call the elements of RCP(Rn ) (regular closed) polyhedra. If n = 2, we speak of (regular closed) polygons. Polyhedra may be regarded as 'well-behaved' or, in topologists' parlance, 'tame.' In particular, every polyhedron has finitely many connected components, a property which is not true of regular closed sets in general.

The topological constraint languages considered here all employ a countably infinite collection of variables r1, r2, . . . The language C features binary predicates = and C, together with the individual constants 0, 1 and the function symbols +, ·, -. The terms τ and formulas ϕ of C are given by:

The language B is defined analogously, but without the predicate C. If S ⊆ RC(T) for some topological space T, an interpretation over S is a function ·I mapping variables r to elements rI ∈ S. We extend ·I to terms τ by setting 0I = ∅, 1I = T , (τ1 + τ2)I = τ I 1 + τ I 2 , etc. We write I |= τ1 = τ2 iff τ I 1 = τ I 2 , and I |= C(τ1, τ2) iff τ I 1 ∩ τ I 2 ̸= ∅. We read C(τ1, τ2) as 'τ1 contacts τ2.' The relation |= is extended to non-atomic formulas in the obvious way. A formula ϕ is satisfiable over S if I |= ϕ for some interpretation I over S.

Turning to languages with connectedness, we define Bc and Cc to be the extensions of B and C with the unary predicate c. We set I |= c(τ) iff τ I is connected in the topological space under consideration. Similarly, we define Bc◦ and Cc◦ to be the extensions of B and C with the predicate c◦ , setting I |= c◦ (τ) iff (τ I )◦ is connected. Sat(L, S) is the set of Lformulas satisfiable over S, where L is one of Bc, Cc, Bc◦ or Cc◦ (the topological space is implicit in this notation, but will always be clear from context). We shall be concerned with Sat(L, S), where S is RC(Rn ) or RCP(Rn ) for n = 2, 3.

To illustrate, consider the Bc◦ -formulas ϕk given by

One can show that ϕ3 is satisfiable over RC(Rn ), n ≥ 2, but not over RC(R), as no three intervals with non-empty, disjoint interiors can be in pairwise contact. Also, ϕ5 is satisfiable over RC(Rn ), for n ≥ 3, but not over RC(R2 ), as the graph K5 is non-planar. Thus, Bc◦ is sensitive to the dimension of the space. Or again, consider the Bc◦ -formula

One can show that (2) is satisfiable over RC(Rn ), for any n ≥ 2 (see, e.g., Fig. 1), but not over RCP(Rn ). Thus Bc◦ is sensitive to tameness in Euclidean spaces. It is

known [Kontchakov et al., 2010b] that, for the Euclidean plane, the same is true of Bc and Cc: there is a Bc-formula satisfiable over RC(R2 ), but not over RCP(R2 ). (The example required to show this is far more complicated than the Bc◦ -formula (2).) In the next section, we prove that any of Bc, Cc and Cc◦ contains formulas satisfiable over RC(Rn ), for every n ≥ 2, but only by regions with infinitely many components. Thus, all four of our languages are sensitive to tameness in all dimensions greater than one.

3 Regions with InfinitelyMany Components

Fix n ≥ 2 and let d0, d1, d2, d3 be regions partitioning Rn :

We construct formulas forcing the di to have infinitely many connected components. To this end we require non-empty regions ai contained in di, and a non-empty region t:

The configuration of regions we have in mind is depicted in Fig. 2, where components of the di are arranged like the layers of an onion. The 'innermost' component of d0 is surrounded by a component of d1, which in turn is surrounded by a component of d2, and so on. The region t passes through every layer, but avoids the ai. To enforce a configuration of this sort, we need the following three formulas, for 0 ≤ i ≤ 3:

where ⌊k⌋ = kmod4. Formulas (5) and (6) ensure that each component of ai is in contact with a⌊i+1⌋, while (7) ensures that no component of di can touch any component of d⌊i+2⌋ .

Denote by ϕ∞ the conjunction of the above constraints. Fig. 2 shows how ϕ∞ can be satisfied over RC(R2 ). By cylindrification, it is also satisfiable over any RC(Rn ), for n > 2.

The arguments of this section are based on the following property of regular closed subsets of Euclidean spaces:

Lemma 1 If X ∈ RC(Rn ) is connected, then every component of -X has a connected boundary.

The proof of this lemma, which follows from [Newman, 1964], can be found in [Kontchakov et al., 2011]. The result fails for other familiar spaces such as the torus.

Theorem 2 There is a Cc-formula satisfiable over RC(Rn ), n ≥ 2, but not by regions with finitely many components.

Proof. Let ϕ∞ be as above. To simplify the presentation, we ignore the difference between variables and the regions they stand for, writing, for example, ai instead of aIi . We construct a sequence of disjoint components Xi of d⌊i⌋ and open sets Vi connecting Xi to Xi+1 (Fig. 3). By the first conjunct of (4), let X0 be a component of d0 containing points in a0. Suppose Xi has been constructed. By (5) and (6), Xi is in contact with a⌊i+1⌋. Using (7) and the fact that Rn is locally connected, one can find a component Xi+1 of d⌊i+1⌋ which has points in ai+1, and a connected open set Vi such that Vi ∩ Xi and Vi ∩Xi+1 are non-empty, but Vi ∩ d⌊i+2⌋ is empty.

. . .

Figure 3: The sequence {Xi, Vi}i≥0 generated by ϕ∞. (Si+1 and Ri+1 are the 'holes' of Xi+1 containing Xi and Xi+2.)

To see that the Xi are distinct, let Si+1 and Ri+1 be the components of -Xi+1 containing Xi and Xi+2, respectively. It suffices to show Si+1 ⊆ S◦ i+2 . Note that the connected set Vi must intersect δSi+1. Evidently, δSi+1 ⊆ Xi+1 ⊆ d⌊i+1⌋ . Also, δSi+1 ⊆ -Xi+1; hence, by (3) and (7), δSi+1 ⊆ di ∪d⌊i+2⌋ . By Lemma 1, δSi+1 is connected, and therefore, by (7), is entirely contained either in d⌊i⌋ or in d⌊i+2⌋. Since Vi∩δSi+1 ̸= ∅ and Vi∩d⌊i+2⌋ = ∅, we have δSi+1 ̸⊆ d⌊i+2⌋ , so δSi+1 ⊆ di. Similarly, δRi+1 ⊆ di+2. By (7), then, δSi+1∩δRi+1 = ∅, and since Si+1 and Ri+1 are components of the same set, they are disjoint. Hence, Si+1 ⊆ (-Ri+1)◦ , and since Xi+2 ⊆ Ri+1, also Si+1 ⊆ (-Xi+2)◦ . So, Si+1 lies in the interior of a component of -Xi+2, and since δSi+1 ⊆Xi+1 ⊆ Si+2, that component must be Si+2. ❑

Now we show how the Cc-formula ϕ∞ can be transformed to Cc◦ - and Bc-formulas with similar properties. Note first that all occurrences of c in ϕ∞ have positive polarity. Let ϕ◦∞ be the result of replacing them with the predicate c◦ . In Fig. 2, the connected regions mentioned in (5) are in fact interior-connected; hence ϕ◦∞ is satisfiable over RC(Rn ). Since interior-connectedness implies connectedness, ϕ◦∞ entails ϕ∞, and we obtain:

Corollary 3 There is a Cc◦ -formula satisfiable over RC(Rn ), n ≥ 2, but not by regions with finitely many components.

To construct a Bc-formula, we observe that all occurrences of C in ϕ∞ are negative. We eliminate these using the predicate c. Consider, for example, the formula ¬C(ai, t) in (6). By inspection of Fig. 2, one can find regions r1, r2 satisfying

On the other hand, (8) entails ¬C(ai, t). By treating all other non-contact relations similarly, we obtain a Bc-formula ψ∞ that is satisfiable over RC(Rn ), and that entails ϕ∞. Thus:

Corollary 4 There is a Bc-formula satisfiable over RC(Rn ), n ≥ 2, but not by regions with finitely many components.

Obtaining a Bc◦ analogue is complicated by the fact that we must enforce non-contact constraints using c◦ (rather than c). In the Euclidean plane, this can be done using planarity constraints; see [Kontchakov et al., 2011].

Theorem 5 There is a Bc◦ -formula satisfiable over RC(R2 ), but not by regions with finitely many components.

Theorem 2 and Corollary 4 entail that, if L is Bc or Cc, then Sat(L, RC(Rn )) ̸= Sat(L, RCP(Rn )) for n ≥ 2. Theorem 5 fails for RC(Rn ) with n ≥ 3 (Sec. 5). However, we know from (2) that Sat(Bc◦ , RC(Rn )) ̸= Sat(Bc◦ , RCP(Rn )) for all n ≥ 2. Theorem 2 fails in the 1D case; moreover, Sat(L, RC(R)) = Sat(L, RCP(R)) only in the case L = Bc or Bc◦ [Kontchakov et al., 2010b].

4 Undecidability in the Plane

Let L be any of Bc, Cc, Bc◦ or Cc◦ . In this section, we show, via a reduction of the Post correspondence problem (PCP), that Sat(L, RC(R2 )) is r.e.-hard, and Sat(L, RCP(R2 )) is r.e.- complete. An instance of the PCP is a quadruple w = (S, T,w1,w2) where S and T are finite alphabets, and each wi is a word morphism from T ∗ to S∗ . We may assume that S = {0, 1} and wi(t) is non-empty for any t ∈ T. The instance w is positive if there exists a non-empty τ ∈ T ∗ such that w1(τ) = w2(τ). The set of positive PCP-instances is known to be r.e.-complete. The reduction can only be given in outline here: for details, see [Kontchakov et al., 2011].

To deal with arbitrary regular closed subsets of RC(R2 ), we use the technique of 'wrapping' a region inside two bigger ones. Let us say that a 3-region is a triple a = (a, ˙a, ¨a) of elements of RC(R2 ) such that 0 ̸= ¨a ≪ ˙a ≪ a, where r ≪ s abbreviates ¬C(r,-s). It helps to think of a = (a, ˙a, ¨a) as consisting of a kernel, ¨a, encased in two protective layers of shell. As a simple example, consider the sequence of 3-regions a1, a2, a3 depicted in Fig. 4, where the innermost regions form a sequence of externally touching polygons. When describing arrangements of 3-regions, we use

the variable r for the triple of variables (r, ˙r, ¨ r), taking the conjuncts ¨ r ̸= 0, ¨ r ≪ ˙r and ˙r ≪ r to be implicit. As with ordinary variables, we often ignore the difference between 3region variables and the 3-regions they stand for.

For k ≥ 3, define the formula stack(a1, . . . , ak) by

Thus, the triple of 3-regions in Fig. 4 satisfies stack(a1, a2, a3). This formula plays a crucial role in our proof. If stack(a1, . . . , ak) holds, then any point p0 in the inner shell ˙a1 of a1 can be connected to any point pk in the kernel ¨ak of ak via a Jordan arc γ1 · · · γk whose ith segment, γi, never leaves the outer shell ai of ai. Moreover, each γi intersects the inner shell ˙ai+1 of ai+1, for 1 ≤ i < k.

This technique allows us to write Cc-formulas whose satisfying regions are guaranteed to contain various networks of arcs, exhibiting almost any desired pattern of intersections. Now recall the construction of Sec. 3, where constraints on the variables d0, . . . , d3 were used to enforce 'cyclic' patterns of components. Using stack(a1, . . . , ak), we can write a formula with the property that the regions in any satisfying assignment are forced to contain the pattern of arcs having the form shown in Fig. 5. These arcs define a 'window,' containing a sequence {ζi} of 'horizontal' arcs (1 ≤ i ≤ n), each connected by a corresponding 'vertical arc,' ηi, to some point on the 'top edge.' We can ensure that each ζi is included in a region a⌊i⌋, and each ηi (1 ≤ i ≤ n) in a region b⌊i⌋, where ⌊i⌋ now indicates i mod 3. By repeating the construction, a second pair of arc-sequences, {ζ ′ i } and {η′i} (1 ≤ i ≤ n′ ) can be established, but with each η′i connecting ζ ′ i to the 'bottom edge.' Again, we can ensure each ζ ′ i is included in a region a′⌊i⌋ and each η′i in a region b′⌊i⌋ (1 ≤ i ≤ n′ ). Further, we can ensure that the final horizontal arcs ζn and ζ ′n′ (but no others) are joined by an arc ζ ∗ lying in a region z∗ . The crucial step is to match up these arc-sequences. To do so, we write ¬C(a′i , bj) ∧ ¬C(ai, b′j ) ∧ ¬C(bi + b′i , bj + b′j + z∗ ), for all i, j (0 ≤ i, j < 3, i ̸= j). A simple argument based on planarity considerations then ensures that the upper and lower sequences of arcs must cross (essentially) as shown in Fig. 6. In particular, we are guaranteed that n = n′ (without specifying the value n), and that, for all 1 ≤ i ≤ n, ζi is connected by ηi (and also by η′i ) to ζ ′ i .

Having established the configuration of Fig. 6, we write (bi ≤ l0 + l1) ∧ ¬C(bi · l0, bi · l1), for 0 ≤ i < 3, ensuring that each ηi is included in exactly one of l0, l1. These inclusions naturally define a word σ over the alphabet {0, 1}. Next, we write Cc-constraints which organize the sequences of arcs {ζi} and {ζ ′ i } (independently) into consecutive blocks. These blocks of arcs can then be put in 1-1 correspondence using essentially the same construction used to put the individual arcs in 1-1 correspondence. Each pair of corresponding blocks can now be made to lie in exactly one region from a collection t1, . . . , tℓ. We think of the tj as representing the letters of the alphabet T, so that the labelling of the blocks with these elements defines a word τ ∈ T ∗ . It is then straightforward to write non-contact constraints involving the arcs ζi ensuring that σ = w1(τ) and non-contact constraints involving the arcs ζ ′ i ensuring that σ = w2(τ). Let ϕw be the conjunction of all the foregoing Cc-formulas. Thus, if ϕw is satisfiable over RC(R2 ), then w is a positive instance of the PCP. On the other hand, if w is a positive instance of the PCP, then one can construct a tuple satisfying ϕw over RCP(R2 ) by 'thickening' the above collections of arcs into polygons in the obvious way. So, w is positive iff ϕw is satisfiable over RC(R2 ) iff ϕw is satisfiable over RCP(R2 ). This shows r.e.-hardness of Sat(Cc, RC(R2 )) and Sat(Cc, RCP(R2 )). Membership of the latter problem in r.e. is immediate because all polygons may be assumed to have vertices with rational coordinates, and so may be effectively enumerated. Using the techniques of Corollaries 3-4 and Theorem 5, we obtain:

The complexity of Sat(L, RC(R3 )) remains open for the languages L ∈ {Bc, Cc◦ , Cc}. However, as we shall see in the next section, for Bc◦ it drops dramatically.

5 Bc◦ in 3D

In this section, we consider the complexity of satisfying Bc◦ - constraints by polyhedra and regular closed sets in threedimensional Euclidean space. Our analysis rests on an important connection between geometrical and graph-theoretic interpretations. We begin by briefly discussing the results of [Kontchakov et al., 2010a] for the polyhedral case.

Recall that every partial order (W, R), where R is a transitive and reflexive relation on W, can be regarded as a topological space by taking X ⊆ W to be open just in case x ∈ X and xRy imply y ∈ X. Such topologies are called Aleksandrov spaces. If (W,R) contains no proper paths of length greater than 2, we call (W,R) a quasi-saw (Fig. 8). If, in addition, no x ∈ W has more than two proper R-successors, we call (W, R) a 2-quasi-saw. The properties of 2-quasi-saws we need are as follows [Kontchakov et al., 2010a]:

• satisfiability of Bc-formulas in arbitrary topological spaces coincides with satisfiability in 2-quasi-saws, and is EXPTIME-complete;
• X ⊆ W is connected in a 2-quasi-saw (W,R) iff it is interior-connected in (W, R).

The following construction lets us apply these results to the problem Sat(Bc◦ , RCP(R3 )). Say that a connected partition in RCP(R3 ) is a tuple X1, . . . ,Xk of non-empty polyhedra having connected and pairwise disjoint interiors, which sum to the entire space R3 . The neighbourhood graph (V,E) of this partition has vertices V = {X1, . . . , Xk} and edges E = {{Xi,Xj} | i ̸= j and (Xi +Xj)◦ is connected} (Fig. 7). One can show that every connected graph is the neighbour-

hood graph of some connected partition in RCP(R3 ). Furthermore, every neighbourhood graph (V,E) gives rise to a 2-quasi-saw, namely, (W0 ∪ W1,R), where W0 = V , W1 = {zx,y | {x, y} ∈ E}, and R is the reflexive closure of {(zx,y, x), (zx,y, y) | {x, y} ∈ E}. From this, we see that (i) a Bc◦ -formula ϕ is satisfiable over RCP(R3 ) iff (ii) ϕ is satisfiable over a connected 2-quasi-saw iff (iii) the Bcformula ϕ· , obtained from ϕ by replacing every occurrence of c◦ with c, is satisfiable over a connected 2-quasi-saw. Thus, Sat(Bc◦ , RCP(R3 )) is EXPTIME-complete.

The picture changes if we allow variables to range over RC(R3 ) rather than RCP(R3 ). Note first that the Bc◦ -formula (2) is not satisfiable over 2-quasi-saws, but has a quasi-saw model as in Fig. 8. Some extra geometrical work will show

now that (iv) a Bc◦ -formula is satisfiable over RC(R3 ) iff (v) it is satisfiable over a connected quasi-saw. And as shown in [Kontchakov et al., 2010a], satisfiability of Bc◦ -formulas in connected spaces coincides with satisfiability over connected quasi-saws, and is NP-complete.

Theorem 7 The problem Sat(Bc◦ , RC(R3 )) is NP-complete. Proof. From the preceding discussion, it suffices to show that (v) implies (iv) for any Bc◦ -formula ϕ. So suppose A |= ϕ, with A based on a finite connected quasi-saw (W0 ∪ W1, R), where Wi contains all points of depth i ∈ {0, 1} (Fig. 8). Without loss of generality we will assume that there is a special point z0 of depth 1 such that z0Rx for all x of depth 0. We show how A can be embedded into RC(R3 ).

Take pairwise disjoint closed balls B1x , for x of depth 0, and pairwise disjoint open balls Dz, for all z of depth 1 except z0 (we assume the Dz are disjoint from the B1x ). Let Dz0 be the closure of the complement of all B1x and Dz. We expand the B1x to sets Bx forming a connected partition in RC(R3 ) (i.e. they sum to R3 , and their interiors are nonempty, connected and pairwise disjoint). To construct the Bx, let q1, q2, . . . be an enumeration of all the points in the interiors of any of the Dz with rational coordinates. For x ∈ W0, we set Bx to be (⋃k≥1 Bk x )- , where the regular closed sets Bk x are defined inductively as follows (Fig. 9). Suppose, for k ≥ 1, Bk x has been defined for all x ∈ W0. Let qi be the first point in the list q1, q2, . . . that is not in any Bk x yet. If qi is in the interior of some Dz, take a closed ball in the interior of Dz centred on qi and disjoint from the Bk x . Now pick some x such that zRx, and expand Bk x by the closed ball around qi together with a closed 'rod' connecting it to B1x , in such a way that the rod is disjoint from the rest of the Bk x ; the result is denoted by Bk+1 x . Consider the function f mapping regular closed sets X ⊆ W to RC(R3 ), defined by f (X) = ∑x∈X∩W0 Bx. Since the Bx form a partition, f preserves +, ·, -, 0 and 1. And since, for all z, ∑{Bx | zRx} is interior connected, f preserves interior-connectedness. By carefully adding extra balls and rods in the construction of the Bk x , we can further ensure that non-interior-connected elements of RC(W,R) are mapped to non-interior connected elements of RC(R3 ) (for details, see [Kontchakov et al., 2011]). Defining an interpretation I over RC(R3 ) by setting rI = f(rA) then secures I |= ϕ. ❑

The remarkably diverse computational behaviour of Bc◦ over RC(R3 ), RCP(R3 ) and RCP(R2 ) can be explained as follows. To satisfy a Bc◦ -formula ϕ in RC(R3 ), it suffices to find polynomially many points in the regions mentioned in ϕ (witnessing non-emptiness or non-interior-connectedness constraints), and then to 'inflate' those points to (possibly interior-connected) regular closed sets using the technique of Fig. 9. By contrast, over RCP(R3 ), one can write a Bc◦ - formula analogous to (8) stating that two interior-connected polyhedra do not share a 2D face. Such 'face-contact' constraints can be used to generate constellations of exponentially many polyhedra simulating runs of alternating Turing machines on polynomial tapes, leading to EXPTIMEhardness. Finally, over RCP(R2 ), planarity considerations endow Bc◦ with the extra expressive power required to enforce full non-contact constructs (not possible in higher dimensions), and thus to encode the PCP as sketched in Sec. 4.

6 Conclusion

This paper investigated topological constraint languages featuring connectedness predicates and Boolean operations on regions. Unlike their less expressive cousins, RCC8 and RCC5, such languages are highly sensitive to the spaces over which they are interpreted, and exhibit more challenging computational behaviour. Specifically, we demonstrated that the languages Cc, Cc◦ and Bc contain formulas satisfiable over RC(Rn ), n ≥ 2, but only by regions with infinitely many components. Using a related construction, we proved that the satisfiability problem for any of Bc, Cc, Bc◦ and Cc◦ , interpreted either over RC(R2 ), or over its polygonal subalgebra, RCP(R2 ), is undecidable. Finally, we showed that the satisfiability problem for Bc◦ , interpreted over RC(R3 ), is NPcomplete, which contrasts with EXPTIME-completeness for RCP(R3 ). The complexity of satisfiability for Bc, Cc and Cc◦ over RC(Rn ) or RCP(Rn ) for n ≥ 3 remains open. The obtained results rely on certain distinctive topological properties of Euclidean spaces. Thus, for example, the argument of Sec. 3 is based on the property of Lemma 1, while Sec. 4 similarly relies on planarity considerations. In both cases, however, the moral is the same: the topological spaces of most interest for Qualitative Spatial Reasoning exhibit special characteristics which any topological constraint language able to express connectedness must take into account.

The results of Sec. 4 pose a challenge for Qualitative Spatial Reasoning in the Euclidean plane. On the one hand, the relatively low complexity of RCC8 over disc-homeomorphs suggests the possibility of usefully extending the expressive power of RCC8 without compromising computational properties. On the other hand, our results impose severe limits on any such extension. We observe, however, that the constructions used in the proofs depend on a strong interaction between the connectedness predicates and the Boolean operations on regular closed sets. We believe that by restricting this interaction one can obtain non-trivial constraint languages with more acceptable complexity. For example, the extension of RCC8 with connectedness constraints is still in NP for both RC(R2 ) and RCP(R2 ) [Kontchakov et al., 2010b].

Acknowledgments. This work was partially supported by the U.K. EPSRC grants EP/E034942/1 and EP/E035248/1.