  We consider the quantifier-free languages, Bc and Bc0, obtained by augmenting
the signature of Boolean algebras with a unary predicate representing,
respectively, the property of being connected, and the property of having a
connected interior. These languages are interpreted over the regular closed
sets of n-dimensional Euclidean space (n greater than 1) and, additionally,
over the regular closed polyhedral sets of n-dimensional Euclidean space. The
resulting logics are examples of formalisms that have recently been proposed in
the Artificial Intelligence literature under the rubric "Qualitative Spatial
Reasoning." We prove that the satisfiability problem for Bc is undecidable over
the regular closed polyhedra in all dimensions greater than 1, and that the
satisfiability problem for both languages is undecidable over both the regular
closed sets and the regular closed polyhedra in the Euclidean plane. However,
we also prove that the satisfiability problem for Bc0 is NP-complete over the
regular closed sets in all dimensions greater than 2, while the corresponding
problem for the regular closed polyhedra is ExpTime-complete. Our results show,
in particular, that spatial reasoning over Euclidean spaces is much harder than
reasoning over arbitrary topological spaces.
