Cardinal directions: a comparison of direction relation matrix and objects interaction matrix

Li, S; Liu, W

Cardinal directions: a comparison of direction relation matrix and objects interaction matrix

Li, S

Liu, W

Permalink

Publication Type:: Journal Article
Citation:: International Journal of Geographical Information Science, 2015, 29 (2), pp. 194 - 216
Issue Date:: 2015-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (1.6 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Liu, W	en_US
dc.date.issued	2015-01-01	en_US
dc.identifier.citation	International Journal of Geographical Information Science, 2015, 29 (2), pp. 194 - 216	en_US
dc.identifier.issn	1365-8816	en_US
dc.identifier.uri	http://hdl.handle.net/10453/138862
dc.description.abstract	© 2014 Taylor & Francis. How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.	en_US
dc.relation.ispartof	International Journal of Geographical Information Science	en_US
dc.relation.isbasedon	10.1080/13658816.2014.954580	en_US
dc.subject.classification	Geological & Geomatics Engineering	en_US
dc.title	Cardinal directions: a comparison of direction relation matrix and objects interaction matrix	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	29	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	0909 Geomatic Engineering	en_US
utslib.for	0406 Physical Geography and Environmental Geoscience	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	open_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	29	en_US

Abstract:

© 2014 Taylor & Francis. How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.

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

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