  The theoretical properties of qualitative spatial reasoning in the RCC8
framework have been analyzed extensively. However, no empirical investigation
has been made yet. Our experiments show that the adaption of the algorithms
used for qualitative temporal reasoning can solve large RCC8 instances, even if
they are in the phase transition region -- provided that one uses the maximal
tractable subsets of RCC8 that have been identified by us. In particular, we
demonstrate that the orthogonal combination of heuristic methods is successful
in solving almost all apparently hard instances in the phase transition region
up to a certain size in reasonable time.
