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:
Filename Description Size
Thumbnail2009000936OK.pdf1.19 MB
Adobe PDF
Full metadata record
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 ( All rights reserved.
Please use this identifier to cite or link to this item: