Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity

AAAI Press
Publication Type:
Conference Proceeding
Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence - vol 2, 2009, pp. 854 - 859
Issue Date:
Full metadata record
Files in This Item:
Filename Description SizeFormat
2009000727OK.pdf2.52 MBAdobe PDF
Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from both calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculiwas very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.
Please use this identifier to cite or link to this item: