Reasoning with Cardinal Directions: An Efficient Algorithm

DSpace/Manakin Repository

Search OPUS


Advanced Search

Browse

My Account

Show simple item record

dc.contributor.author Zhang, X
dc.contributor.author Liu, W
dc.contributor.author Li, S
dc.contributor.author Ying, M
dc.contributor.editor Fox, D
dc.contributor.editor Gomes, CP
dc.date.accessioned 2010-05-28T10:05:09Z
dc.date.issued 2008-01
dc.identifier.citation Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1, 2008, 1 pp. 387 - 392
dc.identifier.isbn 978-1-57735-368-3
dc.identifier.other E1UNSUBMIT en_US
dc.identifier.uri http://hdl.handle.net/10453/11504
dc.description.abstract 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).
dc.publisher AAAI Press
dc.title Reasoning with Cardinal Directions: An Efficient Algorithm
dc.type Conference Proceeding
dc.parent Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1
dc.journal.volume 1
dc.journal.number en_US
dc.publocation USA en_US
dc.identifier.startpage 387 en_US
dc.identifier.endpage 392 en_US
dc.cauo.name FEIT.Faculty of Engineering & Information Technology en_US
dc.conference Verified OK en_US
dc.conference National Conference of the American Association for Artificial Intelligence
dc.for 0801 Artificial Intelligence and Image Processing
dc.personcode 103396
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 National Conference of the American Association for Artificial Intelligence en_US
dc.date.activity 20080713 en_US
dc.date.activity 2008-07-13
dc.location.activity Chicago, Illinois, USA en_US
dc.description.keywords Constraint Satisfaction; 11. Knowledge Representation en_US
dc.description.keywords Constraint Satisfaction
dc.description.keywords 11. Knowledge Representation
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 Closed (ID: 3)


Files in this item

This item appears in the following Collection(s)

Show simple item record