Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming (CP'02), volume 2470 of LNCS, pages 341--355. Springer, September 2002.

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions and study the problem of checking the consistency of a set of cardinal direction constraints. We present the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm we prove that the consistency checking of a set of basic cardinal direction constraints can be performed in O(n^5) time while the consistency checking of an unrestricted set of cardinal direction constraints is NP-complete. Finally, we briefly discuss some extensions to the basic model.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.