Reasoning with Cardinal Directions: An Efficient Algorithm

AAAI Press
Publication Type:
Conference Proceeding
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1, 2008, 1 pp. 387 - 392
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2009000936OK.pdf1.19 MB
Adobe PDF
Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer 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).
Please use this identifier to cite or link to this item: