Reasoning with Cardinal Directions: An Efficient Algorithm

UTSePress Research/Manakin Repository

Search UTSePress Research


Advanced Search

Browse

My Account

Show simple item record

dc.contributor.author Zhang, Xiaotong en_US
dc.contributor.author Liu, Weiming en_US
dc.contributor.author Li, Sanjiang en_US
dc.contributor.author Ying, Mingsheng en_US
dc.contributor.editor Dieter Fox and Carla P. Gomes en_US
dc.date.accessioned 2010-05-28T10:05:09Z
dc.date.available 2010-05-28T10:05:09Z
dc.date.issued 2008 en_US
dc.identifier 2009000936 en_US
dc.identifier.citation Zhang Xiaotong et al. 2008, 'Reasoning with Cardinal Directions: An Efficient Algorithm', AAAI Press, USA, pp. 387-392. en_US
dc.identifier.issn 978-1-57735-368-3 en_US
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). en_US
dc.language English en_US
dc.publisher AAAI Press en_US
dc.relation.isbasedon NA en_US
dc.title Reasoning with Cardinal Directions: An Efficient Algorithm en_US
dc.parent Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1 en_US
dc.journal.volume 1 en_US
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.for 080100 en_US
dc.personcode 0000054787 en_US
dc.personcode 116198 en_US
dc.personcode 106033 en_US
dc.personcode 103396 en_US
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.location.activity Chicago, Illinois, USA en_US
dc.description.keywords Constraint Satisfaction; 11. Knowledge Representation en_US
dc.staffid 103396 en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record