Reasoning with cardinal directions: An efficient algorithm
- Publication Type:
- Conference Proceeding
- Proceedings of the National Conference on Artificial Intelligence, 2008, 1 pp. 387 - 392
- Issue Date:
Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egen-hofer proposed a formal model, called 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. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with disconnected regions, in which case the current best algorithm is of time complexity O(n5).Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Please use this identifier to cite or link to this item: