Reasoning about cardinal directions between extended objects: The NP-hardness result

Publication Type:
Journal Article
Artificial Intelligence, 2011, 175 (18), pp. 2155 - 2169
Issue Date:
Filename Description Size
Thumbnail2011000653OK.pdf609.05 kB
Adobe PDF
Full metadata record
The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of complete networks of basic CDC constraints is tractable, while reasoning with the CDC in general is NP-hard. This paper shows, however, that if some constraints are unspecified, then consistency checking of incomplete networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem. © 2011 Elsevier B.V. All rights reserved.
Please use this identifier to cite or link to this item: