Reasoning with Cardinal Directions: An Efficient Algorithm

Abstract

Direction relations between extended spatial objects are im-portant 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 at-tracted increasing interest from areas such as artificial intelli-gence, 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 dis-connected regions, in which case the current best algorithm is of time complexity O(n5).