Reasoning about cardinal directions between extended objects

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

Reasoning about cardinal directions between extended objects

Liu, W Zhang, X Li, S

Ying, M

Permalink

Publication Type:: Journal Article
Citation:: Artificial Intelligence, 2010, 174 (12-13), pp. 951 - 983
Issue Date:: 2010-08-01

Closed Access

	Filename	Description	Size
	2009006629OK.pdf		1.33 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	Liu, W	en_US
dc.contributor.author	Zhang, X	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	2010-08-01	en_US
dc.identifier.citation	Artificial Intelligence, 2010, 174 (12-13), pp. 951 - 983	en_US
dc.identifier.issn	0004-3702	en_US
dc.identifier.uri	http://hdl.handle.net/10453/13492
dc.description.abstract	Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a relation model, known as the cardinal direction calculus (CDC), for representing direction relations between connected plane regions. The 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 the consistency of complete networks of basic CDC constraints, and proves that reasoning with the CDC is in general an NP-complete problem. For a consistent complete network of basic CDC constraints, our algorithm returns a 'canonical' solution in cubic time. This cubic algorithm is also adapted to check the consistency of complete networks of basic cardinal constraints between possibly disconnected regions. © 2010 Elsevier B.V. All rights reserved.	en_US
dc.relation.ispartof	Artificial Intelligence	en_US
dc.relation.isbasedon	10.1016/j.artint.2010.05.006	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Reasoning about cardinal directions between extended objects	en_US
dc.type	Journal Article
utslib.citation.volume	12-13	en_US
utslib.citation.volume	174	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	1702 Cognitive Sciences	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.issue	12-13	en_US
pubs.publication-status	Published	en_US
pubs.volume	174	en_US

Abstract:

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a relation model, known as the cardinal direction calculus (CDC), for representing direction relations between connected plane regions. The 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 the consistency of complete networks of basic CDC constraints, and proves that reasoning with the CDC is in general an NP-complete problem. For a consistent complete network of basic CDC constraints, our algorithm returns a 'canonical' solution in cubic time. This cubic algorithm is also adapted to check the consistency of complete networks of basic cardinal constraints between possibly disconnected regions. © 2010 Elsevier B.V. All rights reserved.

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

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