Reasoning about Cardinal Directions between Extended Objects
Article, Preprint
English
OPEN
Zhang, Xiaotong
;
Liu, Weiming
;
Li, Sanjiang
;
Ying, Mingsheng
(2009)
 Publisher: Elsevier BV

Journal:
Artificial Intelligence
(issn: 00043702, vol:
174, pp:
951983)

Related identifiers:
doi: 10.1016/j.artint.2010.05.006

Subject:
Computer Science  Artificial Intelligence  Artificial Intelligence
Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, known as Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks, and proves that reasoning with CDC is in general an NPComplete problem. For a consistent network of basic CDC constraints, our algorithm also returns a 'canonical' solution in cubic time. This cubic algorithm is also adapted to cope with cardinal directions between possibly disconnected regions, in which case currently the best algorithm is of time complexity O(n^5).

References
(3)
[25] B. Nebel and H.J. Burckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. Journal of the ACM, 42(1):43{66, 1995.
[26] D.A. Randell, Z. Cui, and A.G. Cohn. A spatial logic based on regions and connection. In Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning (KR92), pages 165{176, 1992.
[27] J. Renz. Maximal tractable fragments of the Region Connection Calculus: A complete analysis. In D. Dean, editor, Proceedings of the Sixteenth International Joint Conference on Arti cial Intelligence (IJCAI99), pages 448{454. Morgan Kaufmann, 1999.

Metrics