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

DSpace/Manakin Repository

Search OPUS


Advanced Search

Browse

My Account

Show simple item record

dc.contributor.author Liu, W
dc.contributor.author Li, S
dc.contributor.author Renz, J
dc.contributor.editor Craig Boutilier
dc.date.accessioned 2010-05-28T10:05:12Z
dc.date.issued 2009-01
dc.identifier.citation Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence - vol 2, 2009, pp. 854 - 859
dc.identifier.isbn 978-1-57735-426-0
dc.identifier.other E1 en_US
dc.identifier.uri http://hdl.handle.net/10453/11509
dc.description.abstract 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.
dc.publisher AAAI Press
dc.title Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity
dc.type Conference Proceeding
dc.parent Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence - vol 2
dc.journal.number en_US
dc.publocation USA en_US
dc.identifier.startpage 854 en_US
dc.identifier.endpage 859 en_US
dc.cauo.name FEIT.Faculty of Engineering & Information Technology en_US
dc.conference Verified OK en_US
dc.conference International Joint Conference on Artificial Intelligence
dc.for 0801 Artificial Intelligence and Image Processing
dc.personcode 106033
dc.personcode 116198
dc.percentage 100 en_US
dc.classification.name Artificial Intelligence and Image Processing en_US
dc.classification.type FOR-08 en_US
dc.edition en_US
dc.custom International Joint Conference on Artificial Intelligence en_US
dc.date.activity 20090711 en_US
dc.date.activity 2009-07-11
dc.location.activity Pasadena, California, USA en_US
dc.description.keywords Qualitative Spatial Reasoning; RCC8; Rectangle Algebra; Cardinal Direction Calculus; Combination; Topological Relations; Directional Relations en_US
dc.description.keywords Qualitative Spatial Reasoning
dc.description.keywords RCC8
dc.description.keywords Rectangle Algebra
dc.description.keywords Cardinal Direction Calculus
dc.description.keywords Combination
dc.description.keywords Topological Relations
dc.description.keywords Directional Relations
pubs.embargo.period Not known
pubs.organisational-group /University of Technology Sydney
pubs.organisational-group /University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group /University of Technology Sydney/Strength - Quantum Computation and Intelligent Systems
utslib.copyright.status Closed Access
utslib.copyright.date 2015-04-15 12:17:09.805752+10
utslib.collection.history Uncategorised (ID: 363)
utslib.collection.history Closed (ID: 3)


Files in this item

This item appears in the following Collection(s)

Show simple item record