Spatial reasoning with rectangular cardinal relations: the convex tractable subalgebra

Navarrete, Isabel; Morales, Antonio; Sciavicco, Guido; Cárdenas Viedma, María Antonia

Publication:
Spatial reasoning with rectangular cardinal relations: the convex tractable subalgebra

dc.contributor.author	Navarrete, Isabel
dc.contributor.author	Morales, Antonio
dc.contributor.author	Sciavicco, Guido
dc.contributor.author	Cárdenas Viedma, María Antonia
dc.contributor.department	Ingeniería de la Información y las Comunicaciones
dc.date.accessioned	2024-05-22T08:12:57Z
dc.date.available	2024-05-22T08:12:57Z
dc.date.issued	2013-01-03
dc.description	© Springer 2012. This document is the Published version of a Published Work that appeared in final form in Annals of Mathematics and Artificial Intelligence. To access the final edited and published work see https://doi.org/10.1007/s10472-012-9327-5	es
dc.description.abstract	Qualitative spatial representation and reasoning plays a important role in various spatial applications. In this paper we introduce a new formalism, we name RCD calculus, for qualitative spatial reasoning with cardinal direction relations between regions of the plane approximated by rectangles. We believe this calculus leads to an attractive balance between efficiency, simplicity and expressive power, which makes it adequate for spatial applications. We define a constraint algebra and we identify a convex tractable subalgebra allowing efficient reasoning with definite and imprecise knowledge about spatial configurations specified by qualitative constraint networks. For such tractable fragment, we propose several polynomial algorithms based on constraint satisfaction to solve the consistency and minimality problems. Some of them rely on a translation of qualitative networks of the RCD calculus to qualitative networks of the Interval or Rectangle Algebra, and back. We show that the consistency problem for convex networks can also be solved inside the RCD calculus, by applying a suitable adaptation of the path-consistency algorithm. However, path consistency can not be applied to obtain the minimal network, contrary to what happens in the convex fragment of the Rectangle Algebra. Finally, we partially analyze the complexity of the consistency problem when adding non-convex relations, showing that it becomes NP-complete in the cases considered. This analysis may contribute to find a maximal tractable subclass of the RCD calculus and of the Rectangle Algebra, which remains an open problem.	es
dc.format	application/pdf	es
dc.format.extent	42	es
dc.identifier.citation	Annals of Mathematics and Artificial Intelligence, Vol. 67, 2013, pp. 31-70
dc.identifier.doi	https://doi.org/10.1007/s10472-012-9327-5
dc.identifier.issn	Print: 1012-2443
dc.identifier.issn	Electronic: 1573-7470
dc.identifier.uri	http://hdl.handle.net/10201/141736
dc.language	eng	es
dc.publisher	Springer	es
dc.relation	This work has been partially supported by the Spanish Ministry of Science and Innovation (MICINN) and the European Regional Development Fund of the European Commission (FEDER) under grant TIN2009-14372-C03-01, and partially financed by the Spanish MEC through the project 15277/PI/10, funded by Seneca Agency of Science and Technology of the Region of Murcia within the II PCTRM 2007-2010. Guido Sciavicco was also partially founded by the Spanish fellowship ‘Ramon y Cajal’ RYC-2011-07821.	es
dc.relation.publisherversion	https://link.springer.com/article/10.1007/s10472-012-9327-5#citeas	es
dc.rights.accessRights	info:eu-repo/semantics/restrictedAccess
dc.subject	Qualitative spatial reasoning	es
dc.subject	Cardinal direction relations	es
dc.subject	Rectangle algebra	es
dc.subject	Interval Algebra	es
dc.subject	Qualitative constraint networks	es
dc.subject	Constraint satisfaction problems	es
dc.title	Spatial reasoning with rectangular cardinal relations: the convex tractable subalgebra	es
dc.type	info:eu-repo/semantics/article	es
dspace.entity.type	Publication	es