generated instances which leads to the question of phase-transitions (Cheeseman, Kanefsky,
& Taylor, 1991). Is there a parameter for randomly generating instances of the consistency problem of RCC-8 that results in a phase-transition behavior? If so, is it the case that the hardest instances are mainly located in the phase-transition region while the instances not contained in the phase-transition region are easily solvable? In order to generate instances which are harder with a higher probability, we generate two different kinds of instances.  On the one hand we generated instances which contain constraints over all RCC-8 relations, on the other hand we generated instances which contain only constraints over relations which are not contained in any of the maximal tractable subsets. We expect these instances to be harder on average than the former instances.

The algorithmic techniques we use for solving these randomly generated instances are borrowed from similar work on qualitative temporal reasoning (Nebel, 1997; van Beek & Manchak, 1996; Ladkin & Reinefeld, 1992). Additionally, we make use of the fragments of RCC-8, named H 8, Q 8 , and C 8 , that permit polynomial-time inferences (Renz & Nebel, 1999; Renz, 1999). In the backtracking algorithm, which is used to solve the reasoning problem for full RCC-8, we decompose every disjunctive relation into relations of one of these tractable subsets instead of decomposing them into its base relations. This reduces the average branching factor of the backtracking tree from 4.0 for the base relations to 1.4375 for H 8 , to 1.523 for C 8 , and to 1.516 for Q 8 . Although these theoretical savings cannot be observed in our experiments, using the maximal tractable subsets instead of the base relations leads to significant performance improvements.

This paper is structured as follows. In Section 2, we give a brief sketch of the RCC-8 calculus and of the algorithms used for solving instances of RCC-8. In Section 3 we describe the procedure for randomly generating instances, the different heuristics we apply for solving these instances, and how we measure the quality of the heuristics. In Section 4 we evaluate different path-consistency algorithms in order to find the most efficient one to be used for forward-checking in the backtracking search. In Section 5 we observe a phase-transition behavior of the randomly generated instances and show that the instances in the phasetransition region are harder to solve than the other instances. In Section 6 we report on the outcome of running the different heuristics for solving the instances and identify several hard instances whi are mainly located in the phase-transition region. In Section 7 we try to solve the hard instances by orthogonally combining the different heuristics. This turns out to be very effective and leads to a very efficient solution strategy. Finally, in Section 8 we evaluate this strategy by trying to solve very large instances. 1

## 2. The Region Connection Calculus Rcc-8

The Region Connection Calculus (RCC) is a first-order language for representation of and reasoning about topological relationships between extended spatial regions (Randell et al., 1992b). Spatial regions in RCC are non-empty regular subsets of some topological space which do not have to be internally connected, i.e., a spatial region may consist of different disconnected pieces. Different relationships between spatial regions can be defined based on one dyadic relation, the connected relation C(a,b) which is true if the topological closures of the spatial regions a and b share a common point.

1. The programs are available as an online appendix.