
## Acknowledgments

We would like to thank Ronny Fehling for his assistance in developing the programs, Malte Helmert for proof reading the paper, and the three anonymous reviewers for their very hlpful comments.

This research has been supported by DFG as part of the project FAST-QUAL-SPACE, which is part of the DFG special research effort on "Spatial Cognition". The first author has been partially supported by a Marie Curie Fellowship of the European Community programme
"Improving Human Potential" under contract number HPMF-CT-2000-00667. A preliminry version of this paper appeared in the Proceedings of the 13th European Conference on Artificial Intelligence (Renz & Nebel, 1998).

## References

Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., & Stamatiou, Y. (1997).

Random constraint satisfaction: a more accurate picture. In 3rd Conference on the Principles and Practice of Constraint Programming (CP'97), Vol. 1330 of LNCS, pp.

107–120. Springer-Verlag.

Allen, J. F. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM, 26 (11), 832–843.

Bennett, B. (1994). Spatial reasoning with propositional logic. In Doyle, J., Sandewall, E, & Torasso, P. (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference, pp. 51–62, Bonn, Germany. Morgan Kaufmann.

Bennett, B. (1997). Logical Representations for Automated Reasoning about Spatial Relationships. Ph.D. thesis, School of Computer Studies, The University of Leeds.

Cheeseman, P., Kanefsky, B., & Taylor, W. M. (1991). Where the really hard problems are.

In Proceedings of the 12th International Joint Conference on Artificial Intelligence, p. 331–337, Sydney, Australia. Morgan Kaufmann.

Gent, I., MacIntyre, E., Prosser, P., Smith, B., & Walsh, T. (2001). Random constraint ssse Gent, I., MacIntyre, E., Prosser, P., & Walsh, T. (1996). The constrainedness of search. In Proceedings of the 13th National Conference on AI (AAAI'96), pp. 246–252.

Golumbic, M. C., & Shamir, R. (1993). Complexity and algorithms for reasoning about time:
A graph-theoretic approach. Journal of the Association for Computing Machinery, 40(5), 1128-1133.

Grigni, M., Papadias, D., & Papadimitriou, C. (1995). Topological inference. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, pp. 901-906, Montreal, Canada.