Reasoning with cardinal directions: An efficient algorithm

Zhang, X; Liu, W; Li, S; Ying, M

Reasoning with cardinal directions: An efficient algorithm

Zhang, X Liu, W Li, S

Ying, M

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the National Conference on Artificial Intelligence, 2008, 1 pp. 387 - 392
Issue Date:: 2008-12-24

Closed Access

	Filename	Description	Size
	2009000936OK.pdf		1.19 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, X	en_US
dc.contributor.author	Liu, W	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Ying, M https://orcid.org/0000-0003-4847-702X	en_US
dc.date.issued	2008-12-24	en_US
dc.identifier.citation	Proceedings of the National Conference on Artificial Intelligence, 2008, 1 pp. 387 - 392	en_US
dc.identifier.isbn	9781577353683	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 Egen-hofer 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).Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.	en_US
dc.relation.ispartof	Proceedings of the National Conference on Artificial Intelligence	en_US
dc.title	Reasoning with cardinal directions: An efficient algorithm	en_US
dc.type	Conference Proceeding
utslib.citation.volume	1	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
dc.location.activity	Chicago, Illinois, USA	en_US
pubs.embargo.period	Not known	en_US
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 - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	1	en_US

Abstract:

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egen-hofer 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).Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/11504