{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:16:16Z","timestamp":1774685776509,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s10472-012-9327-5","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T10:46:25Z","timestamp":1357123585000},"page":"31-70","source":"Crossref","is-referenced-by-count":16,"title":["Spatial reasoning with rectangular cardinal relations"],"prefix":"10.1007","volume":"67","author":[{"given":"Isabel","family":"Navarrete","sequence":"first","affiliation":[]},{"given":"Antonio","family":"Morales","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Sciavicco","sequence":"additional","affiliation":[]},{"given":"M. Antonia","family":"Cardenas-Viedma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,3]]},"reference":[{"key":"9327_CR1","doi-asserted-by":"crossref","unstructured":"Abdelmoty, A., El-Geresy, B.: A general method for spatial reasoning in spatial databases. In:\u00a0Proceedings of CIKM\u201995, pp.\u00a0312\u2013317 (1995)","DOI":"10.1145\/221270.221600"},{"issue":"11","key":"9327_CR2","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J Allen","year":"1983","unstructured":"Allen, J.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832\u2013843 (1983)","journal-title":"Commun. ACM"},{"key":"9327_CR3","unstructured":"Balbiani, P., Condotta, J., del Cerro, L.: A model for reasoning about bidimensional temporal relations. In:\u00a0Proceedings of KR\u201998, pp.\u00a0124\u2013130 (1998)"},{"issue":"5","key":"9327_CR4","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1093\/logcom\/12.5.885","volume":"12","author":"P Balbiani","year":"2002","unstructured":"Balbiani, P., Condotta, J., del Cerro, L.: Tractability results in the block algebra. J. Log. Comput. 12(5), 885\u2013909 (2002)","journal-title":"J. Log. Comput."},{"issue":"1\u20134","key":"9327_CR5","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.ins.2003.05.008","volume":"164","author":"S Cicerone","year":"2004","unstructured":"Cicerone, S., Felice, P.D.: Cardinal directions between spatial objects: the pairwise-consistency problem. Inf. Sci. 164(1\u20134), 165\u2013188 (2004)","journal-title":"Inf. Sci."},{"issue":"1\u20132","key":"9327_CR6","first-page":"1","volume":"46","author":"A Cohn","year":"2001","unstructured":"Cohn, A., Hazarika, S.: Qualitative spatial representation and reasoning: an overview. Fundam. Inform. 46(1\u20132), 1\u201329 (2001)","journal-title":"Fundam. Inform."},{"key":"9327_CR7","unstructured":"Condotta, J.: The augmented interval and rectangle networks. In:\u00a0Proceedings of KR\u201900, pp.\u00a0571\u2013579 (2000)"},{"issue":"2","key":"9327_CR8","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0004-3702(98)00093-9","volume":"106","author":"T Drakengren","year":"1998","unstructured":"Drakengren, T., Jonsson, P.: A complete classification of tractability in Allen\u2019s algebra relative to subsets of basic relations. Artif. Intell. 106(2), 205\u2013219 (1998)","journal-title":"Artif. Intell."},{"key":"9327_CR9","unstructured":"D\u00fcntsch, I.: A tutorial on relation algebras and their application in spatial reasoning (1999). http:\/\/www.cosc.brocku.ca\/~duentsch\/archive\/relspat.pdf . Invited tutorial, COSIT\u201999"},{"key":"9327_CR10","doi-asserted-by":"crossref","unstructured":"El-Geresy, B., Abdelmoty, A.: Qualitative representations in large spatial databases. Int. Database Eng. Appl. Symp. (2001)","DOI":"10.1109\/IDEAS.2001.938072"},{"issue":"3","key":"9327_CR11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1080\/02693799608902079","volume":"10","author":"A Frank","year":"1996","unstructured":"Frank, A.: Qualitative spatial reasoning: Cardinal directions as an example. Int. J. Geogr. Inf. Sci. 10(3), 269\u2013290 (1996)","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"9327_CR12","unstructured":"Gatterbauer, W., Bohunsky, P.: Table extraction using spatial reasoning on the css2 visual box model. In:\u00a0Proceedings of AAAI-06 (2006)"},{"issue":"1\u20132","key":"9327_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0004-3702(02)00193-5","volume":"137","author":"A Gerevini","year":"2002","unstructured":"Gerevini, A., Renz, J.: Combining topological and size information for spatial reasoning. Artif. Intell. 137(1\u20132), 1\u201342 (2002)","journal-title":"Artif. Intell."},{"issue":"5","key":"9327_CR14","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1145\/174147.169675","volume":"40","author":"M Golumbic","year":"1993","unstructured":"Golumbic, M., Shamir, R.: Complexity and algorithms for reasoning about time: a graph-theoretic approach. J. ACM 40(5), 1108\u20131133 (1993)","journal-title":"J. ACM"},{"key":"9327_CR15","unstructured":"Goyal, R.: Similarity assessment for cardinal directions between extended spatial objects. PhD thesis, University of Maine, Dept. of Spatial Information Science and Engineering (2000)"},{"key":"9327_CR16","doi-asserted-by":"crossref","unstructured":"Goyal, R., Egenhofer, M.: Consistent queries over cardinal directions across different levels of detail. In:\u00a0Proceedings of DEXA 2000, pp.\u00a0876\u2013880 (2000)","DOI":"10.1109\/DEXA.2000.875129"},{"key":"9327_CR17","unstructured":"Guesgen, H.: Spatial Reasoning Based on Allen\u2019s Temporal Logic. Tech. Rep. ICSI TR89-049, International Computer Science Institute (1989)"},{"key":"9327_CR18","doi-asserted-by":"crossref","unstructured":"Hernandez, D.: Qualitative Representation of Spatial Knowledge. Springer-Verlag (1994)","DOI":"10.1007\/BFb0020328"},{"key":"9327_CR19","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"P Ladkin","year":"1994","unstructured":"Ladkin, P., Maddux, R.: On binary constraint problems. J. ACM 41, 435\u2013469 (1994)","journal-title":"J. ACM"},{"issue":"3\u20134","key":"9327_CR20","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1023\/A:1018968024833","volume":"19","author":"P Ladkin","year":"1997","unstructured":"Ladkin, P., Reinefeld, A.: Fast algebraic methods for interval constraint problems. Ann. Math. Artif. Intell. 19(3\u20134), 383\u2013411 (1997)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"2\u20133","key":"9327_CR21","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/A:1009721626239","volume":"3","author":"G Ligozat","year":"1998","unstructured":"Ligozat, G.: Corner relations in allen\u2018s algebra. Constraints 3(2\u20133), 165\u2013177 (1998)","journal-title":"Constraints"},{"issue":"1","key":"9327_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1006\/jvlc.1997.9999","volume":"9","author":"G Ligozat","year":"1998","unstructured":"Ligozat, G.: Reasoning about cardinal directions. J. Vis. Lang. Comput. 9(1), 23\u201344 (1998)","journal-title":"J. Vis. Lang. Comput."},{"key":"9327_CR23","doi-asserted-by":"crossref","unstructured":"Ligozat, G., Renz, J.: What is a qualitative calculus? A general framework. In:\u00a0Proceedings of PRICAI 2004, LNCS, vol.\u00a03157, pp.\u00a053\u201364. Springer (2004)","DOI":"10.1007\/978-3-540-28633-2_8"},{"issue":"18","key":"9327_CR24","doi-asserted-by":"crossref","first-page":"2155","DOI":"10.1016\/j.artint.2011.07.005","volume":"175","author":"W Liu","year":"2011","unstructured":"Liu, W., Li, S.: Reasoning about cardinal directions between extended objects: the np-hardness result. Artif. Intell. 175(18), 2155\u20132169 (2011)","journal-title":"Artif. Intell."},{"key":"9327_CR25","unstructured":"Liu, W., Li, S., Renz, J.: Combining rcc-8 with qualitative direction calculi: algorithms and complexity. In:\u00a0Proceedings of IJCAI-09, pp.\u00a0854\u2013859 (2009)"},{"key":"9327_CR26","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1016\/j.artint.2010.05.006","volume":"174","author":"W Liu","year":"2010","unstructured":"Liu, W., Zhang, X., Li, S., Ying, M.: Reasoning about cardinal directions between extended objects. Artif. Intell. 174, 951\u2013983 (2010)","journal-title":"Artif. Intell."},{"issue":"1","key":"9327_CR27","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A Mackworth","year":"1977","unstructured":"Mackworth, A.: Consistency in networks of relations. Artif. Intell. 8(1), 99\u2013118 (1977)","journal-title":"Artif. Intell."},{"issue":"1","key":"9327_CR28","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","volume":"25","author":"A Mackworth","year":"1985","unstructured":"Mackworth, A., Freuder, E.: The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artif. Intell. 25(1), 65\u201374 (1985)","journal-title":"Artif. Intell."},{"key":"9327_CR29","unstructured":"Navarrete, I., Morales, A., Sciavicco, G., Cardenas, M.: An utility package for rectangular cardinal relations (2011). http:\/\/sites.google.com\/site\/aikespatial\/RCDC"},{"key":"9327_CR30","unstructured":"Navarrete, I., Sciavicco, G.: Spatial reasoning with rectangular cardinal direction relations. In:\u00a0Proceedings of ECAI-2006 Workshop on Spatial and Temporal Reasoning, pp.\u00a01\u201310 (2006)"},{"issue":"3","key":"9327_CR31","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF00137869","volume":"1","author":"B Nebel","year":"1997","unstructured":"Nebel, B.: Solving hard qualitative temporal reasoning problems: evaluating the efficiency of using the ord-horn class. Constraints 1(3), 175\u2013190 (1997)","journal-title":"Constraints"},{"issue":"1","key":"9327_CR32","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B Nebel","year":"1995","unstructured":"Nebel, B., B\u00fcrckert, H.: Reasoning about temporal relations: a maximal tractable subclass of Allen\u2019s interval algebra. J. ACM 42(1), 43\u201366 (1995). The authors provide a software for machine-assisted analysis of Allen\u2019s interval algebra","journal-title":"J. ACM"},{"issue":"4","key":"9327_CR33","first-page":"14","volume":"16","author":"B Nebel","year":"2002","unstructured":"Nebel, B., Scivos, A.: Formal properties of constraint calculi for qualitative spatial reasoning. KI 16(4), 14\u201318 (2002)","journal-title":"KI"},{"issue":"2","key":"9327_CR34","first-page":"129","volume":"4","author":"E Oro","year":"2010","unstructured":"Oro, E., Ruffolo, M., Staab, S.: Sxpath\u2014extending xpath towards spatial querying on web documents. PVLDB 4(2), 129\u2013140 (2010)","journal-title":"PVLDB"},{"key":"9327_CR35","unstructured":"Papadias, D., Kalnis, P., Mamoulis, N.: Hierarchical constraint satisfaction in spatial databases. In:\u00a0Proceedings of AAAI\/IAAI-99, pp.\u00a0142\u2013147 (1999)"},{"issue":"2","key":"9327_CR36","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1080\/136588197242428","volume":"11","author":"D Papadias","year":"1997","unstructured":"Papadias, D., Theodoridis, Y.: Spatial relations, minimum bounding rectangles, and spatial data structures. Int. J. Geogr. Inf. Sci. 11(2), 111\u2013138 (1997)","journal-title":"Int. J. Geogr. Inf. Sci."},{"issue":"15","key":"9327_CR37","doi-asserted-by":"crossref","first-page":"1752","DOI":"10.1016\/j.artint.2008.06.003","volume":"172","author":"DN Pham","year":"2008","unstructured":"Pham, D.N., Thornton, J., Sattar, A.: Modelling and solving temporal reasoning as propositional satisfiability. Artif. Intell. 172(15), 1752\u20131782 (2008)","journal-title":"Artif. Intell"},{"key":"9327_CR38","unstructured":"Randell, D., Cui, Z., Cohn, A.: A spatial logic based on regions and connection. In:\u00a0Proceedings of KR\u201992, pp.\u00a0165\u2013176. Morgan Kaufmann (1992)"},{"key":"9327_CR39","doi-asserted-by":"crossref","unstructured":"Renz, J., Ligozat, G.: Weak composition for qualitative spatial and temporal reasoning. In:\u00a0Proceedings of CP 2005, LNCS, vol.\u00a03709, pp.\u00a0534\u2013548. Springer (2005)","DOI":"10.1007\/11564751_40"},{"key":"9327_CR40","doi-asserted-by":"crossref","unstructured":"Renz, J., Nebel, B.: Qualitative spatial reasoning using constraint calculi. In:\u00a0Handbook of Spatial Logics, pp.\u00a0161\u2013215. Springer (2007)","DOI":"10.1007\/978-1-4020-5587-4_4"},{"key":"9327_CR41","doi-asserted-by":"crossref","unstructured":"Renz, J., Schmid, F.: Customizing qualitative spatial and temporal calculi. In: Orgun, M., Thornton, J. (eds.) AI 2007: Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol.\u00a04830, pp.\u00a0293\u2013304 (2007)","DOI":"10.1007\/978-3-540-76928-6_31"},{"key":"9327_CR42","unstructured":"Samet, H.: Spatial data structures. In:\u00a0Modern Database Systems, pp.\u00a0361\u2013385 (1995)"},{"key":"9327_CR43","doi-asserted-by":"crossref","unstructured":"Schultz, C., Guesgen, H., Amor, R.: Computer-human interaction issues when integrating qualitative spatial reasoning into geographic information systems. In:\u00a0Proceedings of the 7th ACM SIGCHI New Zealand chapter\u2019s international conference on Computer-human interaction (CHINZ 2006), pp.\u00a043\u201351. ACM (2006)","DOI":"10.1145\/1152760.1152766"},{"issue":"12","key":"9327_CR44","doi-asserted-by":"crossref","first-page":"1610","DOI":"10.1109\/TKDE.2005.192","volume":"17","author":"S Skiadopoulos","year":"2005","unstructured":"Skiadopoulos, S., Giannoukos, C., Sarkas, N., Vassiliadis, P., Sellis, T., Koubarakis, M.: Computing and managing cardinal direction relations. IEEE Trans. Knowl. Data Eng. 17(12), 1610\u20131623 (2005)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"9327_CR45","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0004-3702(03)00137-1","volume":"152","author":"S Skiadopoulos","year":"2004","unstructured":"Skiadopoulos, S., Koubarakis, M.: Composing cardinal direction relations. Artif. Intell. 152(2), 143\u2013171 (2004)","journal-title":"Artif. Intell."},{"issue":"1","key":"9327_CR46","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.artint.2004.10.010","volume":"163","author":"S Skiadopoulos","year":"2005","unstructured":"Skiadopoulos, S., Koubarakis, M.: On the consistency of cardinal directions constraints. Artif. Intell. 163(1), 91\u2013135 (2005)","journal-title":"Artif. Intell."},{"key":"9327_CR47","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1016\/0004-3702(92)90011-L","volume":"58","author":"P Beek van","year":"1992","unstructured":"van Beek, P.: Reasoning about qualitative temporal information. Artif. Intell. 58, 728\u2013734 (1992)","journal-title":"Artif. Intell."},{"issue":"3","key":"9327_CR48","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1111\/j.1467-8640.1990.tb00130.x","volume":"6","author":"P Beek van","year":"1990","unstructured":"van Beek, P., Cohen, R.: Exact and approximate reasoning about temporal relations. Comput. Intell. 6(3), 132\u2013147 (1990)","journal-title":"Comput. Intell."},{"key":"9327_CR49","unstructured":"Vilain, M., Kautz, H.: Constraint propagation algorithms for temporal reasoning. In: Proceedings of AAAI-86, pp.\u00a0377\u2013382 (1986)"},{"key":"9327_CR50","unstructured":"Westphal, M., W\u00f6lfl, S.: Qualitative csp, finite csp, and sat: comparing methods for qualitative constraint-based reasoning. In:\u00a0Proceedings of IJCAI-09, pp.\u00a0628\u2013633 (2009)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-012-9327-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-012-9327-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-012-9327-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T15:34:34Z","timestamp":1745940874000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-012-9327-5"}},"subtitle":["The convex tractable subalgebra"],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["9327"],"URL":"https:\/\/doi.org\/10.1007\/s10472-012-9327-5","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}