\documentstyle[jair,twoside,11pt,theapa,graphicx,amssymb,amsbsy]{article}
\input epsf %% at top of file

\jairheading{11}{1999}{361-390}{6/99}{11/99}
\ShortHeadings{The Complexity of Reasoning about Spatial Congruence}
{Cristani}
\firstpageno{361}

\newtheorem{exmp}{Example}
\newtheorem{definition}{Definition}
\newtheorem{criterion}{Criterion}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newenvironment{proof}{{\bf Proof}}{\begin{flushright}$\square$\end{flushright}\noindent}
\newenvironment{example}{\begin{exmp}\end{exmp}}{\begin{flushright}$\square$\end{flushright}\noindent}

\def\B{$\times$}
\def\ISQ{$=\ $}
\def\OPL{$\oplus\ $}
\def\OTI{$\otimes\ $}
\def\bOTI{$\pmb{\otimes}\ $}
\def\REV{$^{\smile}\ $}

\def\EMPTY{$\bot\ $}

\def\CG{$\mathsf{CG}\ $}
\def\CGPP{$\mathsf{CGPP}\ $}
\def\CGPPI{$\mathsf{CGPP}^{-1}\ $}
\def\CNO{$\mathsf{CNO}\ $}

\def\CGa{$\mathsf{CG}$}
\def\CGPPa{$\mathsf{CGPP}$}
\def\CGPPIa{$\mathsf{CGPP}^{-1}$}
\def\CNOa{$\mathsf{CNO}$}

\def\bCG{$\pmb{\mathsf{CG}}\ $}
\def\bCGPP{$\pmb{\mathsf{CGPP}}\ $}
\def\bCGPPI{$\pmb{\mathsf{CGPP}^{-1}}\ $}
\def\bCNO{$\pmb{\mathsf{CNO}}\ $}

\def\CGaCGPP{$\{\mathsf{CG,~CGPP}\}\ $}
\def\CGaCGPPI{$\{\mathsf{CG,~CGPP^{-1}}\}\ $}
\def\CGaCNO{$\{\mathsf{CG,~CNO}\}\ $}
\def\CGPPaCGPPI{$\{\mathsf{CGPP,~CGPP^{-1}}\}\ $}
\def\CGPPaCNO{$\{\mathsf{CGPP,~CNO}\}\ $}
\def\CGPPIaCNO{$\{\mathsf{CGPP^{-1},~CNO}\}\ $}
\def\CGaCGPPaCGPPI{$\{\mathsf{CG, CGPP,~CGPP^{-1}}\}\ $}
\def\CGaCGPPaCNO{$\{\mathsf{CG,~CGPP,~CNO}\}\ $}
\def\CGaCGPPIaCNO{$\{\mathsf{CG,~CGPP^{-1},~CNO}\}\ $}
\def\CGPPaCGPPIaCNO{$\{\mathsf{CGPP,~CGPP^{-1},~CNO}\}\ $}
\def\CGaCGPPaCGPPIaCNO{$\{\mathsf{CG,~CGPP,~CGPP^{-1},~CNO}\}\ $}
\def\UNIVERSAL{$\top$\ }

\def\EMPTYa{$\bot$}
\def\CGaCGPPa{$\{\mathsf{CG,~CGPP}\}$}
\def\CGaCGPPIa{$\{\mathsf{CG,~CGPP^{-1}}\}$}
\def\CGaCNOa{$\{\mathsf{CG,~CNO}\}$}
\def\CGPPaCGPPIa{$\{\mathsf{CGPP,~CGPP^{-1}}\}$}
\def\CGPPaCNOa{$\{\mathsf{CGPP,~CNO}\}$}
\def\CGPPIaCNOa{$\{\mathsf{CGPP^{-1},~CNO}\}$}
\def\CGaCGPPaCGPPIa{$\{\mathsf{CG, CGPP,~CGPP^{-1}}\}$}
\def\CGaCGPPaCNOa{$\{\mathsf{CG,~CGPP,~CNO}\}$}
\def\CGaCGPPIaCNOa{$\{\mathsf{CG,~CGPP^{-1},~CNO}\}$}
\def\CGPPaCGPPIaCNOa{$\{\mathsf{CGPP,~CGPP^{-1},~CNO}\}$}
\def\UNIVERSALa{$\top$}



\def\PR{$\bullet\ $}

\def\EQ{$\mathsf{EQ}\ $}
\def\PO{$\mathsf{PO}\ $}
\def\PP{$\mathsf{PP}\ $}
\def\PPI{$\mathsf{PP}$$^{-1}\ $}
\def\DR{$\mathsf{DR}\ $}
\def\EQaDRaPO{$\{$$\mathsf{EQ,DR,PO}$$\}\ $}
\def\PPaDRaPO{$\{$$\mathsf{PP,DR,PO}$$\}\ $}
\def\PPIaDRaPO{$\{$$\mathsf{PP}$$^{-1}\mathsf{,DR,PO}$$\}\ $}
\def\DRaPO{$\{$$\mathsf{DR,PO}$$\}\ $}
\def\EQaPO{$\{$$\mathsf{EQ,PO}$$\}\ $}
\def\EQaPP{$\{$$\mathsf{EQ,PP}$$\}\ $}
\def\EQaPPI{$\{$$\mathsf{EQ,PP}$$^{-1}\}\ $}
\def\PPaPO{$\{$$\mathsf{PO,PP}$$\}\ $}
\def\PPIaPO{$\{$$\mathsf{PO,PP}$$^{-1}\}\ $}
\def\PPaPPI{$\{$$\mathsf{PP,PP}$$^{-1}\}\ $}
\def\EQaPPaPO{$\{$$\mathsf{EQ,PO,PP}$$\}\ $}
\def\EQaPPIaPO{$\{$$\mathsf{EQ,PO,PP}$$^{-1}\}\ $}
\def\EQaPPaPPI{$\{$$\mathsf{EQ,PP,PP}$$^{-1}\}\ $}
\def\PPaPPIaPO{$\{$$\mathsf{PO,PP,PP}$$^{-1}\}\ $}
\def\EQaPPaPPIaPO{$\{$$\mathsf{EQ,PO,PP,PP}$$^{-1}\}\ $}
 
\begin{document}
\title{The Complexity of Reasoning about Spatial Congruence}

\author{\name Matteo Cristani \email cristani@sci.univr.it\\
       \addr Dipartimento Scientifico e Tecnologico,\\
             Universit\`a di Verona,\\
             C\`a Vignal 2, strada Le Grazie, I-37134 Verona}

\maketitle

\begin{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.
\end{abstract}

\begin{section}{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 \citeyear{Jonsson97},
is probably that spatial reasoning has proved to be
applicable to real-world problems, as in Geographical Information Systems
\cite{Egenhofer91a,Grigni95}, and Molecular Biology \cite{Cui94}.

The specific stress on {\em qualitative} reasoning about space, as observed by Zimmermann 
\citeyear{Zimmermann95}, 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
{\em qualitative morphological reasoning about space}.
The term morphological reasoning is intended to suggest reasoning about the
{\em 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-4 which has been preliminarly analysed by Cristani \citeyear{Cristani97}.

The algebra MC-4 is a Constraint Algebra \cite{Ladkin89}
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 {\em same} spatial 
region. In particular, 
the relation $\mathsf{EQ}$, as defined  by Randell, Cui and Cohn \citeyear{Randell89}, 
and analogously by Egenhofer and Franzosa \citeyear{Egenhofer91b}, becomes {\em identity} under 
the {\em unique name assumption}.
Geometry and topology, conversely, allow other kinds of equivalence 
relations. These relations are weaker than the identity, 
namely the equivalence classes they induce are larger than singletons.

The simplest weakening we can define is the {\em congruence} relation.
Even though,
the relation has been studied \cite{Borgo96,Borgo96a,Cristani97,Mutinelli98},
the complexity of reasoning in subalgebras has not yet been 
deeply investigated.

The reason to introduce this new relation, and to provide an  
algebraic structure to host relations based on it 
(in particular relations in which we compare regions, which, even if they are not congruent, 
can be overlapped by roto-translating one into the interior of the other), is that,
in many cases, the knowledge we have to represent in our systems 
necessarily includes internal structures. 
Consider the following example. 
\begin{example}
A GIS is dedicated to the representation of geographical data about industrial sites.

In the system, the structure of factories can be described by means of various
attributes, including size and shape.
One of the users wants to query the system about the opportunity of moving the factory,
where he works, from the 
present site to a new one.
In the new site prefabricated facilities already exist, and the problem consists of deciding
how to preserve topological layout of the factory and minimise the 
costs of buying new engines, to substitute those which cannot fit with the
new facilities.

In order to reason about these problems the system can be made able to 
represent the qualitative
relations between the old and new site parts, establishing, in particular
whether the spatial regions occupied by the engines are ``congruent'', or
even ``congruent to a part'' of the ones
which can be chosen for hosting them in the new factory's site.

Clearly we cannot use topological information, since a spatial region presently
occupied by an engine is surely disjoint from the region that this
engine is going to occupy in the new site, but this information is insufficient
for deciding whether the new site is able to host the engine itself.

Though metric information can be involved in final decision about moving the 
factory, qualitative reasoning can be used in the initial design phase.

In Figure \ref{factory} we give a pictorial representation of one possible situation
in which, to make decisions, we need to represent spatial information which is not
topological.

\begin{figure}
\begin{center}
\includegraphics{figures/postscript/factory.ps}
\end{center}
\caption{A pictorial representation of the relations to be analysed in a GIS for moving 
a factory from an old to a new site. Note that the production lines of the new facility
may not be suitable for hosting certain engines.}
\label{factory}
\end{figure}
\end{example}

\noindent 
The algebra MC-4 can be used to represent the four basic relations which can be built
on the equivalence relation of congruence: if we consider the roto-translation
of a region $x$ with respect to a region $y$, only four possible situations arise.
\begin{itemize}
\item There is at least one roto-translation in which $x$ coincides with $y$.
The two regions are {\em congruent}.
\item There is at least one roto-translation in which $x$ coincides with a proper part of $y$.
The region $x$ is {\em congruent to a proper part of} $y$.
\item  There is at least one roto-translation in which $y$ coincides with a proper part of $x$.
The region $x$ {\em has a proper part congruent to } $y$.
\item None of the above.
The region $x$ and $y$ {\em cannot be perfectly overlapped}. 
\end{itemize}
We would like to stress here three main aspects of these relations.
\begin{enumerate}
\item \label{verso-rcc}The relations can be established between two spatial regions in any 
position of  space.
There is no specific need for the regions to be close, or to be in any particular
topological relation, provided that the relation is compatible; so these congruence
relations are purely
{\em morphological}.
\item The equality of two regions implies congruence.
The relation of proper part excludes
morphological relations other than ``congruent to a part''. This is not the case for the morphological
side. A region can be congruent to a part of another region, even if they are
disjoint, and the same can happen to congruence, as already stated in point 
\ref{verso-rcc}.
\item Even if two regions are of the same size, there may be the case that the regions
are not congruent. This holds also for partial congruence, being possible that 
a region is smaller than another one but they cannot be overlapped. 
\end{enumerate}
The practical relevance of the algebra can be proved by exhibiting many other examples,
especially coming from GIS. In this paper we deal with the problem of
reasoning about congruence in two-dimensional space domain. 
The kind of congruence we assume is the weakest one: roto-translability.
Three-dimensional congruence is not of the same type. The ``natural'' notion
of three-dimensional congruence is isometry, which is much more general than 
roto-translability. 
For example left and right hands are congruent (under the simplified assumption
that they have the same shape and size), but they cannot be roto-translated 
each into the other one. We concentrate here in two-dimensional reasoning
which may be 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 \ref{Previouswork} describes
related work which has been developed in the area.
Section \ref{spatial-mc4-sect} presents the spatial algebra MC-4,
and Section \ref{max-sect} discusses the classification of tractability we
found for this algebra.
Finally, in Section \ref{concl-sect}, some conclusions are given.
\end{section}

\begin{section}{Previous Work}
\label{Previouswork}

From the perspective of individuating primitives to describe space, a 
significant effort has been lately spent, 
in the direction of defining {\em binary} relations between 
spatial regions, which may be used as a model of space in {\em 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 equivalent, exist in the Artificial Intelligence 
\cite{Randell89,Randell92}
and Spatial Database literatures \cite{Egenhofer90,Egenhofer91b,Franzosa92}.
The Artificial Intelligence model, \cite{Randell89,Randell92}
is known as RCC, where the acronym stands for 
{\bf Region Connection Calculus}. 

The RCC
model is centered on the primitive of ``connection'' as originally suggested
by Clarke \citeyear{Clarke81}. 
Gotts \citeyear{Gotts94} and further Gotts, Gooday and Cohn 
\citeyear{Gotts96} obtained connection to be the only primitive. 
In the original framework \cite{Randell89,Randell92} the model was formulated in
two versions, now called RCC-5 and RCC-8. The RCC-5 model is a model in which
we cannot distinguish between interior and boundary of a
spatial region (so that the external connection may be tangency or overlapping,
for example), while in the RCC-8 model this distinction is possible.

Bennett \citeyear{Bennett94,Bennett95}, used propositional logic
to represent RCC
reasoning problems.
He observed that, given a propositional logic, and interpreting the
truth values of each formula as a spatial region, the language of RCC-5 
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-5 relations are still 
sufficient to represent truth condition at semantical level can be
found: set theory.
Therefore, he applied the result of Cook \citeyear{Cook71}
on NP-completeness of classical propositional logic to the restricted model
RCC-5, proving that deciding the consistency of a Constraint
Satisfaction Problem (CSP) on RCC-5 is an NP-complete problem too.

The complete model of RCC-8, instead, 
can not be analysed in terms of pure set theory, 
because the distinction between boundary-connection and interior-connec\-tion
is possible. This distinction means that the minimal interpretation
in which RCC-8 still provides a correct and complete representation of 
truth
conditions at semantical level requires topology.
Statman \citeyear{Statman79} proved that intuitionistic logic along with
interpretations in set theory forces a topology in the models of a sound  
theory. Bennett proved, thus, that RCC-8 can be used to define
the truth conditions of formulas in an intuitionistic propositional logic.
Statman \citeyear{Statman79} proved that intuitionistic 
propositional logic is PSPACE-complete. However, since we do not need
a complete truth verification procedure, but only a procedure for 
constraint processing, Bennett could reduce the result, proving that also
RCC-8 is NP-complete.

These results, even if they are in general negative for practical purposes,
encouraged researches in the direction of restricted models, in such
a way that at least for certain cases we may process a finite set of RCC 
constraints in polynomial fashion on deterministic machines.
In particular, Nebel \citeyear{Nebel95b} showed
that reasoning with the basic relations of RCC-5 and RCC-8 are tractable
problems. 
Renz and Nebel \citeyear{Renz99a} improved the results above, by showing that there exists a maximal tractable subclass of RCC-5, denoted by $\widehat{\cal{H}}$$_5$, formed by 28 relations out of 32, 
which includes all the basic relations,
and a maximal tractable subclass of RCC-8, denoted by  $\widehat{\cal{H}}$$_8$,
formed by 148 relations out of 256 including the basic relations. 
A {\em maximal tractable subclass} $A$, is a subset of a constraint algebra,
such that
problems defined on $A$ are tractable, while problems defined on proper 
supersets of $A$ are not.
These results have been obtained in a 
similar fashion to the work of Nebel and B{\"u}rckert \citeyear{Nebel95a} on
temporal reasoning.
The result of Renz and Nebel
is anyway incomplete, since he simply proved that there
exists one maximal tractable subclass, and he did not classify {\em every} 
maximal tractable subclasses of RCC-5.
Jonsson and Drakengren \citeyear{Jonsson97} showed that there exist
four maximal tractable subclasses of RCC-5, one including the basic relations.
The result is obtained in a similar fashion to \cite{Drakengren97,Jonsson99}.
A complete analysis of the RCC-8 maximal tractable subclasses including the
basic relations has been provided by Renz in \citeyear{Renz99b}.

Our result is the analogous in MC-4 of Jonsson and Drakengren result for RCC-5.
The MC-4 algebra, we describe in this paper,  is structured in the same way 
as the Algebra of Partially Ordered Time (PO-time algebra), studied by 
Anger, Mitra and Rodriguez.
We would like to stress two main aspects here:
\begin{itemize}
\item The MC-4 algebra has the PO-time algebra are the {\em same} algebraic structure: the
discussion of this paper stands a different interpretation of the PO-time algebra, even
different from the spatial interpretation provided by Anger, Mitra and Rodriguez in their
papers.

\item The computational results we present here can be applied to the PO-time algebra as well,
and they extend the previous findings obtained by Anger, Mitra and Rodriguez.

\end{itemize}

In particular Anger, Mitra and Rodriguez \citeyear{Anger98,Anger99}, proved that path-consistency is
insufficient to ensure consistency for relations in this algebra, and that
there exists a tractable subalgebra of it which can be treated by an $O(n^3)$
algorithm.

Anger, Mitra and Rodriguez \citeyear{Anger99}, showed that deciding the consistency of
a PO-time network is an NP-complete problem by reducing to it the analogous
decision problem on RCC-5.

Some important observations are needed, with respect to the results of Anger, Mitra and Rodriguez:
\begin{itemize}
\item The results on the complexity of PO-time algebra can be applied to 
MC-4, only if we can show that when a MC-4 network is consistent
then we can exhibit a consistent scenario in which vertices of the network
are substituted with spatial regions. Therefore, even if we can show this
correspondence for PO-time algebra too, our NP-completeness
result is independent.
Moreover, the method we used to prove the intractability of MC-4 is 
independent as well, and the main difference is in the way we used to exhibit
problematic algebraic structure. Through this proof we derived a simple way to 
solve the problems whenever possible in polynomial time.
\item The discovery of the tractable subalgebras we indicate by $M_{99}$,
$M_{81}$ and $M_{72}$ in
the present paper, deserves acknowledgement of priority to Anger, Mitra and Rodriguez. 
However, Anger, Mitra and Rodriguez also classified one more algebra, which is 
tractable, but not maximal, since it is contained in $M_{99}$.
Moreover, the algorithms we found for $M_{99}$ and $M_{81}$ are  
substantially different from the one Anger, Mitra and Rodriguez present and 
more efficient, being $O(n^2)$ instead of $O(n^3)$. Therefore
the two algorithmic solutions can be considered as independent results as well.
\item The classification presented here is complete, since we classify 
{\em all} the maximal tractable subalgebras of MC-4, and this is a result which
may be applied to temporal reasoning as well,
since it is obtained by means of algorithms which are completely independent from the
interpretation we give to the relations (either spatial or temporal).
\item The introduction of {\em morphological} relations in spatial reasoning is novel 
too, and the study of spatial congruence deserves, in our opinion, deep investigations
henceforth. The fact that two algebras of spatial and temporal reasoning present substantial
similarities is not a novelty. The RCC model corresponds to
subalgebras of Interval Calculus, as stated by Bennett \citeyear{Bennett94}.
Also Anger, Mitra and Rodriguez stated this property of PO-time algebra with respect to
RCC-5, but their interpretation is completely different from our own, 
the equality of PO-time being interpreted as $\mathsf{EQ}$ in RCC-5, while
we interpret it as congruence.
\end{itemize}
Thus, even though a similar algebraic structure has been partially investigated
before, the present paper presents substantial methodological differences and 
we have obtained results which are independent of or extensions 
to the
ones obtained by Anger, Mitra and Rodriguez.

In the remainder of the paper, when a result can be attributed to Anger, Mitra and Rodriguez we
note it in the text.

\end{section}
\begin{section}{The Spatial Algebra MC-4}
\label{spatial-mc4-sect}
In this section we present the spatial algebra MC-4, which has been previously
presented by Cristani \citeyear{Cristani97} and largely
analysed in by Mutinelli \citeyear{Mutinelli98}.

MC-4 is a {\em Binary Constraint Algebra} (henceforth indicated as a Constraint
Algebra). 
In a Constraint Algebra we have a {\em Constraint Domain} and
an {\em Algebra Base}, which is formed by 
mutually exclusive
relations among elements of the Constraint Domain, 
whose union form the universal relation. The converse of a basic
relation is a basic relation too, and the composition of basic relations is the union
of some basic relations.
A {\em Constraint} is the establishment of one of all possible
unions of basic relations between two variables which vary on the domain.
A constraint is satisfied by an assignment of 
one pair of values of the domain to the variables, so that the pair of
values is in one of the relations of the constraint itself. 
Given a finite set of constraints between two variables, the problem of deciding
whether there exists an assignment to the variables such that all the 
constraints can be simultaneously satisfied is referred to as 
{\em Constraint Satisfaction Problem}, and henceforth indicated as a CSP.

The MC-4 
algebra is formed by all the unions of the four basic relations, which can be
established between two-dimensional spatial regions, from a morphological point of
view, with respect to the equivalence relation of {\em congruence}.

The congruence relation is variously interpreted in geometry. Our interpretation is
the most restrictive one: two regions are congruent {\em iff} they can be rigidly
roto-translated into each other.

A region {\em x}, in this interpretation, may be {\em congruent} ($x$ $\mathsf{CG}$ $y$)
to a region {\em y}, or 
{\em congruent to a part of y} ($x$ $\mathsf{CGPP}$ $y$)
or they {\em cannot be perfectly 
overlapped} ($x$ $\mathsf{CNO}$ $y$). 
The relation {\em congruent to a part of} may also be inverted to
{\em having a part congruent to} ($y$ $\mathsf{CGPP}$$^{-1}$ $x$ {\em iff} $x$ 
$\mathsf{CGPP}$ $y$).

In Figure \ref{congruence-relations} a pictorial representation of the three 
basic relations \CGa, \CGPP \ and \CNO is given.
In Table \ref{transitivity-mc4} we present the composition table of MC-4
showing how the basic relations compose with each other.

\begin{figure}
\begin{center}
\includegraphics{figures/postscript/mc4-fig.ps}
\end{center}
\caption{A pictorial representation of the basic relations of MC-4}
\label{congruence-relations}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}{|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|}
\hline

\bOTI       & \bCG     & \bCGPP          & \bCGPPI         & \bCNO \\
\hline
\bCG       & \CG     & \CGPP          & \CGPPI         & \CNO\\
\hline
\bCGPP     & \CGPP   & \CGPP          & \UNIVERSAL      & \CGPP \ \ \CNO\\
\hline
\bCGPPI    & \CGPPI  & \UNIVERSAL      & \CGPPI         & \CGPPI \ \ \CNO\\
\hline
\bCNO      & \CNO    & \CGPP \ \ \CNO      & \CGPPI \ \ \CNO     & \UNIVERSAL\\
\hline
\end{tabular}
\end{center}
\caption{The composition table of MC-4. The symbol \UNIVERSAL represents the universal
relation $\{\mathsf{CG, CGPP, CGPP^{-1}, CNO}\}$.}
\label{transitivity-mc4}
\end{table}

A CSP can be represented by a {\em Network of Constraints}.
A network of constraints is
a labelled graph $\mathcal{G} = \langle V, \lambda, E \rangle$, where $V$ is a finite set 
of {\em vertices},
$E$ is a binary relation on $V$ whose elements are called {\em edges}, and
$\lambda$ is a {\em labelling function} which maps each vertex of 
$\mathcal{G}$ to a variable, and each edge to a relation of a Constraint Algebra
on a given domain $D$.
Given a network of constraints $\mathcal G$, the problem of deciding the consistency
of $\mathcal G$ is the problem of establishing whether is it possible to 
instantiate each vertex label (the variables) with elements of $D$, in such a way that
all the relations represented in $\mathcal G$ as labels of the edges are simultaneously
satisfied. 
The CSP represented by a network
$\mathcal G$ is often referred to, for the algebra $A$, as A-SAT($\mathcal{G}$).
For the sake of simplicity we refer to the CSP represented by a network $\mathcal G$ on MC-4
as MSAT($\mathcal{G}$).

The main result on the MC-4 algebra, with respect to MSAT,
is unfortunately a negative computational
account.
In general, deciding the consistency  is hard to solve for networks of constraints
between variables representing spatial regions, as stated in Theorem \ref{NP-completeness}.
This result has been already proved by Cristani \citeyear{Cristani97}.

Anger, Mitra and Rodriguez \citeyear{Anger98}, showed that path-consistency cannot be applied
successfully to the Algebra of Partially Ordered Time, which is isomorphic
to MC-4 at the syntactic level.
This is insufficient to prove that the CSP on this algebra is
NP-complete. They showed \cite{Anger99} that PO-time algebra is 
NP-complete. Their proof lies on the $\sigma$ translation, which can be shown
to be analogous, but not identical, to the $\Omega$ translation we introduced here, at the
syntactical level, being completely different at  the semantical one.
However, their proof is insufficient to show that we can arrange spatial
solutions, since the map they defined is purely syntactical.
As already observed by Lemon \citeyear{Lemon96}, the representation of space by
means of relation algebra is not pure, and we can obtain satisfiable
networks which are not realizable in space. 
Our proof, instead, can be applied to spatial interpretations. It can be applied
to nonlinear time temporal interpretations as well, since the syntactic level
is shown to be sufficient for space, and nonlinear time can be interpreted as
space too \cite{Anger99}.

Before getting into the proof of this negative result we need to describe a relevant 
correspondences of the MC-4 algebra to the RCC-5 model, which is also used in the proof
of Theorem \ref{NP-completeness}.
The well known RCC-5 algebra is a Constraint Algebra with 5 basic relations: \EQ,
\DR, \PO, \PP, \PPI. The five relations correspond to the pictorial representation
of Figure \ref{RCC-5-picture}.

\begin{figure}
\begin{center}
\includegraphics{figures/postscript/relations-RCC-5.ps}
\end{center}
\caption{A pictorial representation of the relations of RCC-5.}
\label{RCC-5-picture}
\end{figure}

If two spatial regions are in one of the relations of MC-4, then only certain relations
of RCC-5 can be established between them. Conversely, if certain relations of RCC-5
are established only certain corresponding relations of MC-4 are.
This correspondence, however, is not one-to-one.
Consider, for instance, a region $x$ and a region $y$, such that $x$ \DR $y$, in RCC-5,
namely $x$ is disjoint from $y$. Then, each relation of MC-4 can be established 
between $x$ and $y$. However, if $x$ \PP $y$, namely $x$ is a proper part of $y$, then
only the \CGPP relation can be established between $x$ and $y$.
On the other hand, if two regions are congruent, only the relations
\DR, \PO and \EQ can exist between $x$ and $y$.

In Table \ref{corr-rcc-mc} we set the correspondences between MC-4 basic relations
and RCC-5, while in Table \ref{corr-mc-rcc} we set the correspondences between  
RCC-5 and MC-4.

\begin{table}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Rel. of MC-4 & Rel. of RCC-5 \\
\hline
\CG      & \EQaDRaPO \\
\hline
\CGPP    & \PPaDRaPO \\
\hline
\CGPPI   & \PPIaDRaPO \\
\hline
\CNO     & \DRaPO \\
\hline
\end{tabular}

\caption{The basic relations of MC-4 and their counterparts in RCC-5. The meaning
of the Table is that when a relation of MC-4 is established, then one of the relations
of RCC-5 in second column is established as well.}
\label{corr-mc-rcc}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Rel. of RCC-5 & Rel. of MC-4 \\
\hline
\EQ      & \CG \\
\hline
\PP    & \CGPP \\
\hline
\PPI   & \CGPPI \\
\hline
\PO     & \CGaCGPPaCGPPIaCNO \\
\hline
\DR     & \CGaCGPPaCGPPIaCNO\\
\hline
\end{tabular}

\caption{The basic relations of RCC-5 and their counterparts in MC-4.} 
\label{corr-rcc-mc}
\end{center}
\end{table}

The correspondences of the above Tables are not sufficiently strict, 
to use them in 
proving that MSAT(MC-4) is an NP-complete problem by a direct polynomial 
reduction.
If we consider a CSP on MC-4, the corresponding RCC-5 CSP is not intractable,
since the relations obtained from Table \ref{corr-mc-rcc} do not define an intractable subset
of RCC-5, by means of the complete classification established by Jonsson and Drakengren
\citeyear{Jonsson97}.
Therefore, MSAT(MC-4) is not reducible to RSAT(RCC-5) (the RSAT symbol represents the
satisfiability in RCC models) by the corresponding relation mapping of Table 
\ref{corr-mc-rcc}.

Conversely, we can establish, by means of the above Tables, that among all the possible
regions satisfying the relation $\mathsf{CG}$, 
there exists at least one pair in which the regions
are $\mathsf{EQ}$, that when \CGPP is established, there exists one pair in a 
\PP relation,
and finally that when \CNO is established, we have two regions in a 
\PO relation.
The summary of this correspondence is reported in Table \ref{part-corr-mc-rcc}.

This correspondence is obtained from the definition of basic relations.
Two regions $a$ and $b$ are congruent {\em iff} we can 
roto-translate $a$ by a $T$ in such a way that $T(a)~ \mathsf{EQ}~ $$b$ or
conversely by $T^{\prime}$ so that $T^{\prime}(b)~ \mathsf{EQ}~ $$a$.
Analogously $a$ is congruent to a part of $b$ {\em iff} we can
roto-translate $a$ by $T$ so that $T(a)~ \mathsf{PP}~ $$b$.
Finally two regions are in a \CNO relation {\em iff} they can only be
in a \PO relation or disjoint.

\begin{table}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Rel. of MC-4& Rel. of RCC-5 \\
\hline
\CG      & \EQ \\
\hline
\CGPP    & \PP \\
\hline
\CGPPI   & \PPI \\
\hline
\CNO     & \PO \\
\hline
\end{tabular}

\caption{The basic relations of MC-4 and their counterparts in RCC-5 in the 
special mapping $\Omega$.} 
\label{part-corr-mc-rcc}
\end{center}
\end{table}


The correspondence of Table \ref{part-corr-mc-rcc}
is called $\Omega$, and a Network of Constraints $\mathcal G$ on MC-4
translated in RCC-5 by it is denoted by $\Omega(\mathcal{G})$.
The networks which are labelled on all edges by
basic relations of MC-4 are henceforth called {\em scenarios} of MC-4.

Consider a consistent scenario $S$ of MC-4. Applying the composition 
tables of MC-4 and RCC-5, we clearly derive that
the scenario of RCC-5 $\Omega(S)$ is consistent, when the scenario of
MC-4 does so.
The consequence of above reasoning is the next lemma.

\begin{lemma}
\label{cons-scenario}
If a scenario on MC-4 is consistent, then $\Omega(\mathcal{G})$ is consistent.
\end{lemma}

Ladkin and Maddux \citeyear{Ladkin89}
proved that a network of constraints is consistent
{\em iff} it has a consistent scenario.
Therefore, an immediate consequence of Lemma \ref{cons-scenario} is that
if a network of constraints $\mathcal{G}$ on MC-4 is consistent, then
$\Omega(\mathcal{G})$ is consistent.
We are now able to prove a first theorem.

\begin{theorem}
\label{np-hardness}
{\em MSAT(MC-4)} is NP-hard.
\end{theorem}
\begin{proof}\\
By the observation about existence of consistent scenarios in a Constraint
Algebra due to Mackworth and Freuder \citeyear{Mackworth77}, 
we obtain a polynomial reduction of 
RSAT(RCC-5) to MSAT(MC-4).

It suffices to note that if we can solve MSAT then we can 
solve RCC-5 problems obtained by the $\Omega$ translation as well.
Now, the problems mapped from MC-4 into RCC-5 by means of $\Omega$ can be
trivially inverted by $\Omega^{-1}$, since $\Omega$ is trivially one-to-one.
This means that each problem in the set of relations obtained in RCC-5
by  $\Omega$ corresponds to a problem in MC-4, and vice versa.

The set of relations of RCC-5 translated by $\Omega$ contains \PPaPPI
and \PO. Nebel and Renz \citeyear{Renz99a}, proved that each set of
relations of RCC-5 containing these two relations is intractable.
Therefore the set $\Omega(MC-4)$ is intractable.

This proves that if we are able to solve a problem in MC-4 we can solve a 
problem of a subset of RCC-5 which is intractable. Therefore MSAT(MC-4)
is NP-hard.
\end{proof}
Mackworth and Freuder \citeyear{Mackworth77} also proved that backtracking can
be applied to CSPs. The backtracking algorithm is usually implemented
by a linear non-deterministic technique, being therefore a polynomial algorithm
on non-deterministic machines.

The backtracking technique is applicable to MC-4 as well, so 
we can perform a polynomial solution of MSAT on nondeterministic
machines. This shows that MSAT is in NP, and allows us to claim:
\begin{theorem}
\label{NP-completeness}
{\em MSAT(MC-4)} is NP-complete.
\end{theorem}

Because of this negative result a deep investigation is needed to define
tractable subclasses of  the set of 16 relations which allow us to 
perform polynomial analysis for at least a subset of the networks of constraints
definable on MC-4.

In this paper we give the definition of the three maximal tractable subclasses
of MC-4, exhibiting therefore a complete classification of tractability for the
algebra.
The three maximal tractable subclasses have already been studied by
Anger, Mitra and Rodriguez in \citeyear{Anger99}. 
They obtain maximality
of the algebras, and exhibited $O(n^3)$ algorithms.
We have three main differences here with respect to their paper:
\begin{enumerate}
\item The number of classes we individuated is lower than theirs, because
they found four maximal tractable subclasses. They 
failed to note that one of the four subalgebras is a subset of another one.
In Table \ref{tractable-a99-algebras} the subalgebra $M_{88}$ corresponds to the
fourth algebra of Anger, Mitra and Rodriguez. This subalgebra is tractable, but 
not maximal.
\item The algorithms we exhibit are all $O(n^2)$ while Anger, Mitra and Rodriguez exhibited
only an $O(n^3)$ algorithm for one of the three maximal subsets.
\item Our classification is complete. Thus any subset of MC-4 which is not
a subset of one of the three maximal tractable subalgebras we individuated 
is intractable.
Anger, Mitra and Rodriguez did not find this result, since they did not analyse all the
subalgebras of PO-time algebra, as we did for MC-4.
\end{enumerate}

\end{section}
\begin{section}{Maximal Tractable Subclasses of MC-4}
\label{max-sect}
Given a subset $S$ of a constraint algebra $A$, we indicate
by $\widehat{S}$ the set formed by all the relations of $A$ which can be
written as expressions of the algebra involving only elements of $S$ and
the operations of composition, intersection and converse of relations.
This set is often called the {\em transitive closure} of $S$ with respect
to the operations above. We refer to it as the {\em closure} of $S$.
A set $S$ which coincides with its closure is called a subalgebra.

In the previous section we recall the result on NP-completeness for MC-4.
The first important observation on the complexity of subalgebras
is that, 
when a subalgebra $B$ does not contain the empty relation, then a
network of constraints on $B$ cannot entail a strict contradiction:
then it is consistent.
So far, the problem is necessarily polynomially solvable, because it is
$O(1)$. This is stated in the next lemma.

\begin{lemma}
\label{empty-rel}
Given an algebra $A$, if a subalgebra $B$ of $A$ does not contain the
empty relation, then {\em SAT(B)} is polynomial.
\end{lemma}

The main consequence of Lemma \ref{empty-rel} is that we can limit ourselves
in the analysis of subalgebras in MC-4 to these subalgebras which contain
the empty relation.

Moreover, since a network of constraints represents the relations in an
implicit way, when an edge of a network is not labelled we should interpret it as
representing the universal relation. Therefore, the universal relation should be
a member of the subalgebras to which we are interested in. 
We call
algebras which contain both the empty and
the universal relations {\em expressive algebras}.

There are 102 expressive
subalgebras, we denominate $M_i$ where $i$ varies between 0 to
101.
In Tables 
\ref{Intractable-algebras},
\ref{tractable-cg-algebras},
\ref{tractable-cno-algebras},
\ref{tractable-cgpp-cgppi-algebras},
\ref{tractable-a99-algebras},
\ref{tractable-a81-algebras} of Appendix \ref{tables-102},
the 102 expressive subalgebras of MC-4 are listed.
\begin{lemma}
\label{machine-assisted-102}
Given a subset $A$ of MC-4, $A$ is an expressive subalgebra
{\em iff} $A$ is one of the subalgebras $M_i$ with $i$ between 0 
and 101 .
\end{lemma}
\begin{proof}\\ 
Consider a subset $A$ of MC-4.
We test the closure of $A$ by a LISP program which computes the closure by
composition, intersection and converse of a subset of MC-4, 
and test the presence of empty and universal
relation in $A$ by the obvious membership test. The LISP procedure 
{\texttt TRANSITIVE-CLOSURE} is listed in Online
Appendix 1, which accompanies this article.
The test succeeds for the subalgebras $M_i$ with $i$ between 
0 and 101 and fails for all the other $2^{16}-102 = 65434$ subsets of MC-4.
The claim is therefore proved.
\end{proof}

The following technical lemma
shows that some of
the 102 subalgebras individuated above are NP-hard.
There are 20 subalgebras of the 102 which are intractable by Lemma
\ref{technical-lemma}.
The algebras are presented in Table \ref{Intractable-algebras} of Appendix \ref{tables-102}.
The proof of Lemma \ref{Intractable-algebras} is a trivial consequence of the
proof of Theorem \ref{NP-completeness}.

\begin{lemma}
\label{technical-lemma}
Given a subalgebra $A$ of MC-4, if $A$ contains the relations
\CNO and \{$\mathsf{CGPP,}$ $\mathsf{CGPP}$$^{-1}$\} then {\em MSAT(A)} is NP-hard.
\end{lemma}

\noindent In the next three subsections we show that three maximal tractable subclasses
of MC-4 can be found, so that the only intractable algebras are the 20
listed in Table \ref{Intractable-algebras} of Appendix \ref{tables-102}.
\begin{subsection}{The \CG-complete Subalgebra $M_{72}$}
When proving that the class $R_{28}^{5}$ is tractable, Jonsson and Drakengren
\citeyear{Jonsson97} observed that any subalgebra of RCC-5 containing only relations
including \EQ is tractable. This result applies also to MC-4 with respect to the relation \CGa,
and also to the relations \CNOa, \CGPPaCGPPIa, \CGaCNOa, 
$\{\mathsf{CG, CGPP,~CGPP^{-1}}\}$.

The only relevant cases are \CG, \CNO and 
$\{\mathsf{CGPP,~CGPP^{-1}}\}\ $, since the other
two cases are included in two of the former three.
An algebra formed by relations which all contain \CG and by the relation \EMPTY is 
tractable, because we can obtain an inconsistency {\em iff} we explicitly
have an edge labelled by \EMPTY in the network. Deciding the consistency is therefore
an $O(n^2)$ problem.

\begin{figure}
{\bf \large{\textsf{ALGORITHM M72-CONSISTENCY}}}\\ \\
\begin{tabular}{lp{6cm}}
{\bf \textsf{INPUT:}}  &  \textsf{A constraint network $\cal{T}$ on $M_{72}$}\\ \\
{\bf \textsf{OUTPUT:}} & \textsf{Yes if $\cal{T}$ has a solution formed by spatial  
regions of $\mathbb{R}$$^2$, no if not.} \\ \\
\end{tabular}
\begin{tabular}{p{1cm}p{1cm}p{1cm}p{1cm}p{4cm}}
\textsf{1.} & {\bf \textsf{For}} & \multicolumn{3}{l}{\textsf{each edge in $\cal{T}$, $\langle x , y \rangle$}} \\
            &                    & \multicolumn{3}{l}{\bf \textsf{If}} 
\textsf{the label on  $\langle x , y \rangle$
				   is \EMPTY \ {\bf then} return inconsistency}\\
&       {\bf \textsf{Loop}} \\
2. & \multicolumn{2}{l}\textsf{Return consistency}\\
\\
\\
\end{tabular}
\caption{\label{ALGO-CG-cons} Algorithm M72-consistency.}
\end{figure}

\begin{center}
$M_{72} = \{ $\EMPTYa, \CGa, \CGaCGPPa, \CGaCGPPIa, \CGaCNOa, \CGaCGPPaCGPPIa, \CGaCGPPaCNOa,
\CGaCGPPIaCNOa, \UNIVERSALa$\}$.
\end{center}
Since no contradiction derives from a relation in $M_{72}$ except for $\bot$,
Algorithm $M_{72}$-consistency (see Figure \ref{ALGO-CG-cons})
solves the consistency checking problem for
a network of constraints on $M_{72}$.
Thus we can claim the following theorem:

\begin{theorem}
\label{algorithm-cg-complete}
Algorithm $M_{72}$-consistency correctly decides the consistency of a network of constraints $\cal{T}$
on
$M_{72}$ in $O(n^2)$ time where $n$ is the number of vertices in $\cal{T}$.
\end{theorem}

\noindent The immediate consequence of Theorem \ref{algorithm-cg-complete} is the 
following theorem:

\begin{theorem}
\label{M72-tract}
{\em MSAT($M_{72}$)} is polynomial.
\end{theorem}

\noindent The subalgebras  included in 
$M_{72}$ are in Table \ref{tractable-cg-algebras} 
of Appendix \ref{tables-102}.

The 13 subalgebras of Table  \ref{tractable-cg-algebras} are not the only subalgebras which can be theoretically obtained
based on the method incorporated in Algorithm $M_{72}$-consistency. The same algorithm can be applied to
subalgebras formed only with relations containing a symmetrical relation in MC-4 and the empty relation.
Then we can also prove the polynomiality for
subalgebras of relations all containing $\mathsf{CNO}$, or all containing 
$\{\mathsf{CGPP,CGPP}$$^{-1}\}$,
if such subalgebras exist. 
The subalgebra formed by relations containing \CNO and the empty relation is $M_{78}$, the subalgebra formed only by relations
containing \CGPPaCGPPI is $M_{31}$. In Table \ref{tractable-cno-algebras} and in Table \ref{tractable-cgpp-cgppi-algebras} of Appendix \ref{tables-102}
the subalgebras of $M_{78}$ and of $M_{31}$ are shown.

In the next subsection we introduce a maximal tractable subclass which includes $M_{78}$, and in subsection
\ref{section-m81} we introduce an algebra containing $M_{31}$, so that the proof of tractability for subalgebras in
Tables \ref{tractable-cno-algebras} and \ref{tractable-cgpp-cgppi-algebras} can be derived
from these tables as well. Conversely, the subalgebra $M_{72}$ is neither a subalgebra of $M_{99}$ nor a subalgebra of $M_{81}$,
so Theorem \ref{algorithm-cg-complete} is an independent result.
\end{subsection}
\begin{subsection}{The Maximal Tractable Subclass $M_{99}$}
\label{section-m99}
We look for a maximal tractable subalgebra containing all the basic relations. The best candidate, based on Table
\ref{Intractable-algebras}, is $M_{99}$, which is the only algebra formed by more than 13 relations which can be polynomial,
because we did not show that it is NP-hard by reducing it to an intractable problem over RCC-5.
\begin{center}
$M_{99} = \{ $\EMPTYa, \CGa, \CGPPa, \CGPPIa, \CNOa, 
\CGaCGPPa, \CGaCGPPIa, \CGaCNOa, \CGPPaCNOa, \CGPPIaCNOa,
\CGaCGPPaCNOa,
\CGaCGPPIaCNOa, \UNIVERSALa$\}$. 
\end{center}

Fortunately, we can prove the tractability of $M_{99}$, so it is maximal based on the fact that all
algebras containing the basic relations are either intractable by Table \ref{Intractable-algebras} or subsets
of $M_{99}$.

Consider the subset of $M_{99}$, 
\begin{center}
$G_{99} = \{$\CGaCGPPa, \CGaCNOa, \CGPPaCGPPIaCNOa$\}$.
\end{center}
The following claim holds.

\begin{lemma}
\label{translation-lemma-m99}
$\widehat{G_{99}} = M_{99}$.
\end{lemma}
\begin{proof}\\ 
The following expressions represent valid implementations of relations in $M_{99}$
using only elements of $G_{99}$ and the operators of composition,
intersection and converse.\\
\begin{center}
\begin{tabular}{|l|p{4cm}p{0.2cm}p{7cm}|}
\hline
t.1. & \EMPTY 		& \ISQ & \CGaCGPP $\oplus$ \CGaCNO $\oplus$ \CGPPaCGPPIaCNO\\
\hline
t.2. & \CG 		& \ISQ & \CGaCGPP \OPL \CGaCGPP\REV\\
\hline
t.3. & \CGPP 		& \ISQ & \CGaCGPP \OPL \CGPPaCGPPIaCNO\\
\hline
t.4. & \CGPPI 		& \ISQ & \CGaCGPP\REV \OPL \CGPPaCGPPIaCNO\\
\hline
t.5. & \CNO 		& \ISQ & \CGaCNO \OPL \CGPPaCGPPIaCNO\\
\hline
t.6. & \UNIVERSAL 	& \ISQ & \CGaCGPP \OTI \CGPPaCGPPIaCNO\\
\hline
t.7. & \CGaCGPPI       & \ISQ & \CGaCGPP\REV \\
\hline
t.8. & \CGPPaCNO       & \ISQ & (\CGaCGPP \OTI \CGaCNO) \OPL \CGPPaCGPPIaCNO\\
\hline
t.9. & \CGPPIaCNO      & \ISQ & (\CGaCGPP\REV \OTI \CGaCNO) \OPL \CGPPaCGPPIaCNO\\
\hline
t.10. & \CGaCGPPaCNO    & \ISQ & \CGaCGPP \OTI \CGaCNO\\
\hline
t.11. & \CGaCGPPIaCNO 	& \ISQ & \CGaCGPP\REV \OTI \CGaCNO\\
\hline
\end{tabular}
\end{center}
\end{proof}
\noindent A network of constraints $\cal{T}$ on $M_{99}$,
implemented by means of Lemma 
\ref{translation-lemma-m99} is denoted henceforth by $\Psi_{99}(\cal{T}$$)$.

We can derive a contradiction from a network of constraints {\em iff}
the network derives two relations $R_1$ and $R_2$, between one pair of vertices
such that $R_1 \cap R_2 = \varnothing$.
The ways in which  a contradiction can be derived in networks labelled
by relations of $M_{99}$, based on the intersections of relations (except
the empty relation which obviously generates a contradiction by itself)
are:\\
\begin{center}
\begin{tabular}{|l|lcl|}
\hline
a)  & \CG & \OPL & \CGPP\\
\hline
b)  & \CG & \OPL & \CNO \\
\hline
c)  & \CG & \OPL & \CGPPaCNO\\
\hline
d)  & \CG & \OPL & \CGPPaCGPPIaCNO\\
\hline
e)  & \CGPP & \OPL & \CGPPI\\
\hline
f)  & \CGPP & \OPL & \CNO\\
\hline
g)  & \CGPP & \OPL & \CGaCGPPI\\
\hline
h)  & \CGPP & \OPL & \CGaCNO \\ 
\hline
i)  & \CGPP & \OPL & \CGPPIaCNO \\
\hline
l) & \CGPP & \OPL & \CGaCGPPIaCNO \\
\hline
m) & \CNO & \OPL & \CGaCGPP \\
\hline
n) & \CGaCGPP & \OPL & \CGPPIaCNO \\
\hline
\end{tabular}
\label{tab-contr99}
\end{center}
\ \\
\noindent 
This is simply obtained by considering all 
pairs of relations in $M_{99}$ whose intersection is empty.

In $G_{99}$ the contradictions are only:
\\
\CGaCGPP \OPL \CGaCGPP\REV \OPL \CGPPaCGPPIaCNO and \\
\CGaCGPP \OPL \CGaCNO \OPL \CGPPaCGPPIaCNO.
\\
Henceforth we represent the relation \CGaCGPP by $\precsim$,
the relation \CGaCNO by  $^{\bowtie}_{\sim}$ and the relation 
\CGPPaCGPPIaCNO by $\not \sim$.
Since any path in which labels are all $\precsim$ 
corresponds to the representation
of $\precsim$ between each pair of vertices in the path, and 
$\precsim$ \OTI $^{\bowtie}_{\sim}$ 
\ISQ $\precsim$, the possible expressions for contradictions in $G_{99}$
are ($\precsim^n$ \OTI $\precsim^{-n}$) \OPL $\not \sim$ and 
($\precsim^n$ \OTI $\precsim^{-(n-k)}$ \OTI $^{\bowtie}_{\sim}$
\OTI $\precsim^{-k}$)
\OPL $\not \sim$. Hence, a cycle ($\precsim^n$ \OTI $\precsim^{-n}$)
is called a $\precsim$-cycle, while a cycle
($\precsim^n$ \OTI $\precsim^{-(n-k)}$ \OTI $^{\bowtie}_{\sim}$ 
\OTI $\precsim^{-k}$)
is called a quasi $\precsim$-cycle.
The graph representation of these two different contradictory
situations in $G_{99}$ is showed in Figure \ref{fig_bot99}. 
A $\precsim$-cycle and a quasi $\precsim$-cycle, in $M_{99}$ 
force the elements involved in the cycle to be all in the
relation \CG.

We can now show that the contradictions represented in $G_{99}$ are the 
only contradictions which can be obtained by the implementation suggested in Lemma
\ref{translation-lemma-m99}.
This is very important, because 
we may perform consistency checking by simply checking all cycles.
This result is stated in the next lemma.
\begin{lemma} \label{cycle-lemma-m99}
Given a network of constraints $\cal{T}$ on $M_{99}$, 
$\cal{T}$ is inconsistent {\em iff} $\Psi_{99}(\cal{T}$$)$ contains
either a $\precsim$-cycle of a quasi $\precsim$-cycle, 
and two 
vertices of one cycle are connected by an
edge labelled by $\not \sim$.
\end{lemma}
\begin{proof} {\bf (Sketch)}\\
Case by case, the contradictions from
a) to n), as in the table above, generate one of the two situations of the claim. 

For example, the contradiction a) 
\CG \OPL \CGPP, generates 
\begin{center}
(\CGaCGPP \OTI \CGaCGPP\REV) \OPL (\CGaCGPP \OPL \CGPPaCGPPIaCNO)
\end{center} 
which
is a $\precsim$-cycle in which two 
vertices are connected by an edge labelled by $\not \sim$, as stated
in the claim. All the other cases behave in the same way as can be easily
checked by the reader.

Conversely, if a contradiction derives from one of the possible implicit
ways of representing relations in $M_{99}$, the implementation also
produces one of the cases of the claim.
In particular we have that, in $M_{99}$, 
$\mathsf{CG}^n$ 		\ISQ 	\CG, 
$\mathsf{CGPP}^n$ 		\ISQ 	\CGPP,
$(\mathsf{CGPP}^{-1})^n$      	\ISQ    \CGPPI ,
$\{\mathsf{CG, CGPP}\}^n$      	\ISQ    \CGaCGPP and
$\{\mathsf{CG, CGPP}^{-1}\}^n$ 	\ISQ    \CGaCGPPI 
are the only idempotent relations.
The other cases of implicitness can be obtained by considering all the 
$14 \cdot 14 = 196$ pairs of relations in $M_{99}$,
composing and intersecting them.
The implicit cases arising thus are listed in below.
\\
\begin{center}
\begin{tabular}{|l|p{3cm}p{0.2cm}p{7cm}|}
\hline
i.1.  & \CG           & \ISQ & \CGaCGPPa$^n$ \OPL \CGaCGPPIa$^n$\\
\hline
i.2.  & \CG           & \ISQ & \CGaCGPPa$^n$ \OPL \CGaCNO\\
\hline
i.3.  & \CGPP         & \ISQ & \CGaCGPPa$^n$ \OPL \CGPPaCNO\\
\hline
i.4.  & \CNO          & \ISQ & \CGaCNO \OPL \CGPPaCNO\\
\hline
i.5.  & \CNO          & \ISQ & \CGPPaCNO \OPL \CGPPIaCNO\\
\hline
i.6.  & \CNO          & \ISQ & \CGPPaCNO \OPL \CGaCGPPIaCNO\\
\hline
i.7.  & \CGaCNO       & \ISQ & \CGaCGPPaCNO \OPL\ \  \CGaCGPPIaCNO\\
\hline
i.8.  & \CGPPaCNO     & \ISQ & \CGPPa$^n$ \OTI \CNO\\
\hline
i.9.  & \CGPPaCNO     & \ISQ & \CGPPa$^n$ \OTI \CGaCNO\\
\hline
i.10. & \CGPPaCNO     & \ISQ & \CGPPa$^n$ \OTI \CGaCGPPaCNO \\
\hline
i.11. & \CGPPaCNO     & \ISQ & \CGaCGPPa$^n$ \OTI \CNO \\
\hline
i.12. & \CGPPaCNO     & \ISQ & \CGaCGPPaCNO \OPL\ \ \CGPPaCGPPIaCNO\\
\hline
i.13. & \CGaCGPPaCNO  & \ISQ & \CGaCGPPa$^n$ \OTI \CGaCNO\\
\hline
\end{tabular}
\end{center}
\ \\
\noindent Readers may directly express in $G_{99}$ each of these relations
along with the corresponding relation producing a contradiction in
$M_{99}$ and they immediately verify the existence 
of $\precsim$-cycles or quasi $\precsim$-cycle
where one pair of vertices is connected by
an edge labelled by $\not \sim$ for these generated graphs.

For example if we express \CG as implicit relation by i.1. as in table above
(formed by relations
in $G_{99}$), \CGPP as implicit relation by i.3. and \CGPPaCNO \ by $\Psi_{99}$
as in t.8., and consider the contradiction \CG \OPL \CGPP we obtain a quasi
$\precsim$-cycle where two vertices are connected by an
edge labelled by $\not \sim$.
Similarly we can derive the other cases.
\end{proof}

\begin{figure}
\begin{center}
\includegraphics{figures/postscript/bot99.ps}
\end{center}
\caption{Contradictions in $G_{99}$: \{\} indicates $\bot$ 
and R, S, T respectively \CGaCGPPa, \CGaCNO and \CGPPaCGPPIaCNOa.}  
\label{fig_bot99}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{figures/postscript/contr99.ps}
\end{center}
\caption{Contradictions in $M_{99}$: 
R, S, T respectively indicate \CGaCGPPa, \CGaCNO and \CGPPaCGPPIaCNOa.
Letters from a) to n) refer to the table of page \pageref{tab-contr99}.}
\label{fig_contr99}
\end{figure}
We can now exhibit an algorithm which looks for $\precsim$-cycles
and quasi $\precsim$-cycles, and checks about pairs of a cycle being
connected by an edge labelled by $\not \sim$.

In Figure \ref{ALGO-m99} an algorithm able to solve the Consistency Checking Problem 
for networks of constraints labelled by relations in $M_{99}$ is presented.
Based on Lemma \ref{cycle-lemma-m99} we can prove the following theorem.

\begin{figure}
{\bf \large{\textsf{ALGORITHM M99-CONSISTENCY}}}\\ \\
\begin{tabular}{lp{6cm}}
{\bf \textsf{INPUT:}}  & \textsf{A constraint network $\cal{T}$ on $M_{99}$}\\ \\
{\bf \textsf{OUTPUT:}} & \textsf{Yes if $\cal{T}$ has a solution formed by spatial 
regions of $\mathbb{R}$$^2$, no if not.} \\ \\
\end{tabular}
\begin{tabular}{p{1cm}p{1cm}p{1cm}p{1cm}p{4cm}}
\textsf{1.} &\multicolumn{4}{l}{\textsf{{\bf Translate} $\cal{T}$ into the generator set as in
Lemma \ref{translation-lemma-m99}}}\\
\textsf{2.} & \multicolumn{4}{l}{\textsf{{\bf Look} for cycles labelled by 
$\precsim$ and at most one $^{\bowtie}_{\sim}$
}}\\
\textsf{3.} & \multicolumn{4}{l}{\textsf{{\bf Check} whether edges between two 
vertices in one cycle
are not labelled by $\not \sim$}}\\
& \multicolumn{4}{l}{\textsf{otherwise {\bf return} {\em no}.}}\\
\textsf{4.} & \multicolumn{4}{l}{\textsf{{\bf Substitute} vertices of the cycle with one vertex.}}\\ 
\textsf{2.} & \multicolumn{4}{l}{\textsf{{\bf If} there are more cycles {\bf go to} Step 2.,
otherwise {\bf return} {\em yes}.}}\\
\end{tabular}
\caption{Algorithm  M99-consistency}
\label{ALGO-m99}
\end{figure}

\begin{theorem}
\label{theo-algo-m99}
Algorithm M99-CONSISTENCY correctly decides the consistency of a network
of constraints $\cal{T}$ on $M_{99}$ in $O(n^2)$ steps where $n$ is the
number of vertices of $\cal{T}$.
\end{theorem}
\begin{proof}\\
By Lemma \ref{cycle-lemma-m99} we can ensure the correctness of Algorithm
M99-CONSISTENCY. 
The complexity of the algorithm can be derived from the fact that the computation
of strongly connected components is a $O(e)$ problem where $e$ is the number
of edges in the  network. The $\Psi_{99}$ implementation 
adds, in the worst case, $O(e^{\prime})$ edges, where $e^{\prime}$ is
the number of edges in $\cal{T}$, and therefore the number of edges
in $\Psi_{99}(\cal{T}$$)$ is $O(2 \cdot e^{\prime})$, which is
$O(n^2)$.
\end{proof}

\noindent An immediate consequence of Theorem \ref{theo-algo-m99} is the
following theorem:

\begin{theorem}
\label{M99-tract}
{\em MSAT($M_{99}$)} is polynomial.
\end{theorem}


\noindent The subalgebras of MC-4 included in $M_{99}$ are in Table \ref{tractable-a99-algebras} of
Appendix \ref{tables-102}.
\end{subsection}

\begin{subsection}{The Maximal Tractable Subclass $M_{81}$}
\label{section-m81}
The problem of deciding the consistency of a network of constraints on MC-4 is tractable, by means of Tables
\ref{tractable-cg-algebras}, \ref{tractable-cno-algebras}, \ref{tractable-cgpp-cgppi-algebras} and 
\ref{tractable-a99-algebras} for 85 subalgebras. The remainder is formed by 17 subalgebras, each of these  
can be either tractable or intractable.
The set 
\begin{center}
$M_{81}=\{$ \EMPTYa, \CGa, \CGPPa, \CGPPIa, \CGaCGPPa, \CGaCGPPIa, \CGPPaCGPPIa, \CGaCGPPaCGPPIa, \CGPPaCGPPIaCNOa, \UNIVERSALa$\}$
\end{center}
contains all these subalgebras, so that if $M_{81}$ is tractable all these algebras are as well.

By analogy with the schema of the previous section we look for a small generator
set for $M_{81}$. This is $G_{81}$ \ISQ $\{$\CGaCGPPa, \CGaCGPPaCGPPIa, 
\CGPPaCGPPIaCNOa$\}$.
The following lemma states the properties
of $M_{81}$ with respect to $G_{81}$.
\begin{lemma}
\label{translation-lemma-m81}
$\widehat{G_{81}} = M_{81}$.
\end{lemma}
\begin{proof}\\
The following expressions represent valid implementations of relations in $M_{81}$
using only elements of $G_{81}$ and the operators of composition,
intersection and converse.\\
\begin{center}
\begin{tabular}{|l|p{3cm}p{0.2cm}p{7cm}|}
\hline
r.1.  & \EMPTY      & \ISQ & \CGaCGPP \OPL \CGaCGPP\REV \ \ \OPL \CGPPaCGPPIaCNO\\
\hline
r.2.  & \CG         & \ISQ & \CGaCGPP \OPL \CGaCGPP\REV \\
\hline
r.3.  & \CGPP       & \ISQ & \CGaCGPP \OPL \CGPPaCGPPIaCNO \\
\hline
r.4.  & \CGPPI      & \ISQ & \CGaCGPP\REV \OPL \CGPPaCGPPIaCNO \\
\hline
r.5.  & \CGaCGPPI   & \ISQ & \CGaCGPP\REV \\
\hline
r.6.  & \CGPPaCGPPI & \ISQ & \CGaCGPPaCGPPI \OPL \ \ \CGPPaCGPPIaCNO \\
\hline
r.7.  & \UNIVERSAL  & \ISQ & \CGaCGPP \OTI \CGPPaCGPPIaCNO \\
\hline
\end{tabular}
\end{center}
\end{proof}
\noindent The implementation of relations in $M_{81}$ as described in Lemma
\ref{translation-lemma-m81} is denoted by $\Psi_{81}$.
The contradictions in $M_{81}$ are as in the next table.

\begin{center}
\begin{tabular}{|l|lcl|l|lcl|}
\hline
a)  & \CG & \OPL & \CGPP\\
\hline
b)  & \CG & \OPL & \CGPPaCGPPI\\
\hline
c)  & \CG & \OPL & \CGPPaCGPPIaCNO\\
\hline
d)  & \CGPP & \OPL & \CGPPI\\
\hline
e)  & \CGPP & \OPL & \CGaCGPPI \\
\hline
\end{tabular}
\label{tab-81}
\end{center}

The only possible contradiction in $G_{81}$ is 
\begin{center}
\CGaCGPP \OPL \CGaCGPP\REV 
\OPL \CGPPaCGPPIaCNO 
\end{center}
and it corresponds to a $\precsim$-cycle where two
vertices are connected by an edge labelled by $\not \sim$.

\begin{lemma} \label{cycle-lemma-m81}
Given a network of constraints $\cal{T}$ on $M_{81}$, 
$\cal{T}$ is inconsistent {\em iff} $\Psi_{81}(\cal{T}$$)$ contains
a $\precsim$-cycle and two 
vertices of one cycle are connected by an
edge labelled by $\not \sim$.
\end{lemma}
\begin{proof} {\bf (Sketch)}\\
Case by case, the contradictions from
a) to e), as in the table above, generate one of the two cases
claimed here.

For example, the contradiction \CG \OPL \CGPPaCGPPI, is implemented 
\begin{center} 
(\CGaCGPP \OPL \CGaCGPP\REV) \OPL (\CGaCGPPaCGPPI \\
\OPL \CGPPaCGPPIaCNO)
\end{center} 
which
is a $\precsim$-cycle in which two 
vertices are connected by an edge labelled by $\not \sim$, as stated
in the claim. All the other cases behave in the same way as can be easily
checked by the reader.

The only possible ways of
representing implicit relations are provided by the schema of
$\Psi_{81}$. Therefore the claim is proved.
\end{proof}

\begin{figure}
\begin{center}
\includegraphics{figures/postscript/contr81.ps}
\end{center}
\caption{Contradictions in $M_{81}$. 
R, S, T respectively indicate \CGaCGPPa, \CGaCGPPaCGPPIa, \CGPPaCGPPIaCNOa.
Letters from a) to e) refer to the table of page \pageref{tab-81}.}
\label{fig_contr81}
\end{figure}

\begin{figure}
{\bf \large{\textsf{ALGORITHM M81-CONSISTENCY}}}\\ \\
\begin{tabular}{lp{6cm}}
{\bf \textsf{INPUT:}}  & \textsf{A constraint network $\cal{T}$ on $M_{81}$}\\ \\
{\bf \textsf{OUTPUT:}} & \textsf{Yes if $\cal{T}$ has a solution formed by spatial 
regions of $\mathbb{R}$$^2$, no if not.} \\ \\
\end{tabular}
\begin{tabular}{p{1cm}p{1cm}p{1cm}p{1cm}p{4cm}}
\textsf{1.} &\multicolumn{4}{l}{\textsf{{\bf Translate} $\cal{T}$ into the generator set as in 
Lemma \ref{translation-lemma-m81}}}\\
\textsf{2.} & \multicolumn{4}{l}{\textsf{{\bf Look} for cycles labelled by 
$\precsim$
}}\\
\textsf{3.} & \multicolumn{4}{l}{\textsf{{\bf Check} whether edges between two vertices in one cycle 
are not labelled by $\not \sim$}}\\
& \multicolumn{4}{l}{\textsf{otherwise {\bf return} {\em no}.}}\\
\textsf{4.} & \multicolumn{4}{l}{\textsf{{\bf Substitute} vertices of the cycle with one vertex.}}\\
\textsf{2.} & \multicolumn{4}{l}{\textsf{{\bf If} there are more cycles {\bf go to} Step 2.,
otherwise {\bf return} {\em yes}.}}\\
\end{tabular}
\caption{Algorithm  M81-consistency}
\label{ALGO-m81}
\end{figure}

\noindent In Figure \ref{ALGO-m81} an algorithm is presented which solves the problem of consistency checking
for the subalgebra $M_{81}$. 
We can show, in particular, the following claim.

\begin{theorem}
\label{theo-algo-m81}
Algorithm M81-CONSISTENCY correctly decides the consistency of a network
of constraints $\cal{T}$ on $M_{81}$ in $O(n^2)$ steps where $n$ is the
number of vertices of $\cal{T}$.
\end{theorem}
\begin{proof}\\
By Lemma \ref{cycle-lemma-m81} we can ensure the correctness of Algorithm
M81-CONSISTENCY. 
The complexity of the algorithm can be derived from the fact that the computation
of strongly connected components is a $O(e)$ problem where $e$ is the number
of edges in the  network. The $\Psi_{81}$ implementation 
adds, in the worst case, $O(e^{\prime})$ edges, where $e^{\prime}$ is
the number of edges in $\cal{T}$, and therefore the number of edges
in $\Psi_{81}(\cal{T}$$)$ is $O(2 \cdot e^{\prime})$, which is clearly
$O(n^2)$.

\end{proof}
\noindent An immediate consequence of Theorem \ref{algorithm-cg-complete} is the
following

\begin{theorem}
\label{M81-tract}
{\em MSAT($M_{81}$)} is polynomial.
\end{theorem}

\noindent The subalgebras included in
 $M_{81}$ are in Table \ref{tractable-a81-algebras}
of Appendix \ref{tables-102}.


\end{subsection}
\end{section}
\begin{section}{Conclusions}
\label{concl-sect}
We presented a classification of tractability which is complete
for the spatial algebra MC-4. This classification states
that there exist three maximal tractable subalgebras
$M_{72}$, $M_{99}$ and $M_{81}$ which include 92 out of 102
expressive subalgebras of MC-4.

The interest in a complete classifications of tractability,
as already observed by Jonsson and Drakengren \citeyear{Jonsson97},
is determined by the need for a definition of the boundary between tractable
and intractable problems. 
Nebl \citeyear{Nebel99} has suggested that the knowledge of this boundary can be used
either as preprocessing step and as a way to structure the 
backtracking search on such algebras. 

The provision of a complete classification is one step in
researching about constraint algebras. A next step is the individuation
of useful heuristics which give improvements in the 
performances of various techniques.
We are currently exploiting the use of these techniques in association with techniques based on the classification presented
in this paper to obtain efficient reasoning algorithms which
can be used in practice. Preliminary results on path-consistency
are encouraging, but we cannot yet guarantee the percentage
of improvement, since the algebra MC-4 is so simply structured
that for networks randomly chosen it is very hard to obtain
a case where inconsistency is not detectable by path-consistency.
\end{section}
\section*{Acknowledgements}

I would like to thank Elena Mutinelli who developed her Laurea Thesis
 \cite{Mutinelli98}
on the theme of complexity of reasoning about congruence and
first discussed preliminary results which I used
for developing the classification of this paper. 
Her work has been very relevant in reaching my results.

I would also like to thank Bernhard Nebel for some important observations he
made to a student of mine, Alessandro Fin, which improved this work.
Further thanks go to Jochen Renz 
for discussions in the early stages of this work.

I would also like to thank the anonymous referees of the Journal of Artificial
Intelligence Research for their very careful comments and suggestions
which allowed me to make
the presentation simpler and more systematical. Some of the proofs in the paper
have been rewritten thanks to their suggestions.

Finally I would like to thank Tony Cohn for reading a near final version. His
comments have been useful in enhancing both scientific and literary quality
of the paper.

This work has been developed in the context of the National
Project, MURST ex 40\% ``Metodologie e tecnologie per la
gestione di dati e processi su reti internet ed intranet'' (Methods
and technologies for data and process management on internet and intranet)
directed by L. Tanca.

\appendix
\newpage
\section{Tables of the 102 subalgebras of MC-4}
\label{tables-102}
In this section we present the subalgebras of MC-4 organized in separated tables
depending on their characteristics.
In particular Table \ref{Intractable-algebras} shows those subalgebras which are intractable by Lemma \ref{technical-lemma},
Table \ref{tractable-cg-algebras} those which are tractable
by Theorem \ref{algorithm-cg-complete}, and in Tables
\ref{tractable-cno-algebras}, \ref{tractable-cgpp-cgppi-algebras}
those to which Algorithm used in Theorem 
\ref{algorithm-cg-complete} can be applied (which are all
including \CNO or \CGPPaCGPPI).
In Table \ref{tractable-a99-algebras} the subalgebras included in
 $M_{99}$ are displyed, while in Table \ref{tractable-a81-algebras}
we present the subalgebras included in $M_{81}$.
\input{tables.tex}
\clearpage
\bibliographystyle{theapa}
\bibliography{articolo}
\end{document}
