
## 6. Conclusion

In this paper, we have proved that deciding the consistency of basic but possibly incomplete CDC networks is an NP-hard problem. Combined with the tractable result reported in [10], this draws a sharp boundary between the tractable and intractable subclasses of the CDC. It seems that the CDC is the first known qualitative calculus in which reasoning with conjunctive constraints is NP-hard, while reasoning with explicit constraints is in P. Our result is achieved by using a polynomial reduction from 3-SAT, which is also applied to CDCd, the cardinal direction calculus for possibly disconnected regions.

This suggests that the O(n 5) algorithm in [16] is incomplete for checking the consistency of basic CDC networks. Future work will consider approximating methods for solving the consistency decision problem in the CDC.

## References

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

[2] P. Balbiani, J.-F. Condotta, and L. Farinas del Cerro. A new tractable subclass of ˜
the rectangle algebra. In D. Dean, editor, *Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99)*, pages 442–447. Morgan Kaufmann, 1999.

[3] S. Cicerone and P. di Felice. Cardinal directions between spatial objects: the pairwise-consistency problem. *Information Sciences*, 164(1-4):165–188, 2004.

[4] R. Dechter. *Constraint processing*. Morgan Kaufmann Publishers, San Francisco, CA, 2003.

[5] R. Goyal and M.J. Egenhofer. The direction-relation matrix: A representation for directions relations between extended spatial objects. In The Annual Assembly and the Summer Retreat of University Consortium for Geographic Information Systems Science, 1997.

[6] R.K. Goyal. Similarity assessment for cardinal directions between extended spatial objects. PhD thesis, The University of Maine, 2000.

[7] M. Grigni, D. Papadias, and C.H. Papadimitriou. Topological inference. In Proceedings of the Forteenth International Joint Conference on Artificial Intelligence
(IJCAI-95), pages 901–907, 1995.