analysed in terms of roto translation and topological relations The analysis of isometries is left for further work The paper is organised as follows  Section   describes related work which has been developed in the area Section presents the spatial algebra MC and Section discusses the classification of tractability we found for this algebra  Finally in Section some conclusions are given

## 2. Previous Work

From the perspective of individuating primitives to describe space a significant effort has ben lately spent  in the direction of defining binary relations between spatial regions  which may be used as a model of space in qualitative terms  Moreover  it was natural  in the AI
community to use Constraint Processing for reasoning about such binary relations A
specific attention to Constraint Processing emerged in the Spatial Database community and in the community of Geographical Information Science as well Two apparently independently developed models  which can be shown to be essentially tive equivalent exist in the Artificial Intelligence  Randell   
Cohn Randell Cui Cohn and Spatial Database literatures  Egenhofer    Herring   
Egenhofer The Artificial Intelligence model   Randell Franzosa Franzosa     Egenhofer is known as RCC  where the acronym stands for Region Cohn Randell et al Connection Calculus The RCC model is centered on the primitive of  connection" as originally suggested and further Gotts  Gooday and Cohn by Clarke otained Got ts connection to be the only primitive  In the original framework  Randell Cohn the model was formulated in two versions  now called RCC   and Randell et al The RCC   model is a model in which we cannot distinguish between interior RCC
and boundary of a spatial region  so that the external connection may be tangency or overlapping  for example   while in the RCC   model this distinction is possible used propositional logic to represent RCC reasoning problems   He Bennett observed that  given a propositional logic  and interpreting the truth values of each formula as a spatial region the language of RCC is sufficient to express a satisfaction problem at the semantical level This fact however is not due to the spatial interpretation because a non spatial interpretation in which the RCC relations are still sufficient to represent truth condition at semantical level can be found  set theory  Therefore  he applied the on NP completeness of classical propositional logic to the restricted result of Cook model RCC    proving that deciding the consistency of a Constraint Satisfaction Problem CP  on RCC   is an NP complete problem too The complete model of RCC instead  can not be analysed in terms of pure set theory because the distinction between boundary connection and interior connection is possible This distinction means that the minimal interpretation in which RCC still provides a correct and complete representation of truth conditions at semantical level requires topology proved that intuitionistic logic along with interpretations in set theory forces Statman a topology in the models of a sound theory  Bennett proved  thus  that RCC   can be used to define the truth conditions of formulas in an intuitionistic propositional logic   Statman proved that intuitionistic propositional logic is PSPACE complete  However  since