# The Complexity Of Reasoning About Spatial Congruence

## Matteo  Crista Ni

Dipartimento Scientifico e Tecnologico, Universita di Verona, Ca Vignal 2, strada Le Grazie, I-37134 Verona CRISTANI@SCI. U NIV R. IT

## Abstract

In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras.

In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.

## 1. Introduction

Qualitative spatial reasoning has received an increasing amount of interest in the recent literature The main reason for this as already observed by Jonsson and Drakengren is probably that spatial reasoning has proved to be applicable to real world problems  as in Geographical Information Systems  Egenhofer Grigni Papadias Papadimitriou and Molecular Biology   Cui The specific stress on qualitative reasoning about space as observed by Zimmermann is justified by the fact that qualitative spatial relations can be treated as efficiently as their quantitative counterparts but they seem to be closer to the model of relations humans adopt for spatial reasoning Even though qualitative spatial reasoning has an extended literature in spite of its relatively short history  certain aspects of the discipline have been neglected   In particular no exhaustive computational perspective has been developed on qualitative morphological reasoning about space  The term morphological reasoning is intended to suggest reasoning about the internal structure of the objects In the case of spatial reasoning this includes reasoning about the size shape and internal topology of spatial regions The purpose of the present work is to analyse the complexity of reasoning about relations of congruence  either actual or partial  between spatial regions  using the spatial algebra MC
which has been preliminarly analysed by Cristani is a Constraint Algebra  Ladkin Maddux The algebra MC
for qualitative reasoning about the morphological relation of congruence Two spatial regions in the models documented in literature  are considered to be equivalent if and only if they share interior and boundaries  namely if and only if they are the same spatial region  In particular