# Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework

Michael Sioutis, Jean-François Condotta, Yakoub Salhi, Bertrand Mazure, David A. Randell

► To cite this version:

Michael Sioutis, Jean-François Condotta, Yakoub Salhi, Bertrand Mazure, David A. Randell. Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework. 11th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI 2015), Sep 2015, Bayonne, France. pp.130-150, 10.1007/978-3-319-23868-5_10. hal-01385350

HAL Id: hal-01385350

https://inria.hal.science/hal-01385350

Submitted on 21 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Ordering Spatio-Temporal Sequences to meet Transition Constraints: Complexity & Framework*

Michael Sioutis<fnref n="1" />, Jean-François Condotta<fnref n="1" />, Yakoub Salhi<fnref n="1" />, Bertrand Mazure<fnref n="1" />, and David A. Randell<fnref n="2" />

**Abstract.** *Time* and *space* are fundamental concepts of study in Artificial Intelligence and, in particular, Knowledge Representation. In this paper, we investigate the task of ordering a temporal sequence of qualitative spatial configurations to meet certain transition constraints. This ordering is constrained by the use of conceptual neighbourhood graphs defined on qualitative spatial constraint languages. In particular, we show that the problem of ordering a sequence of qualitative spatial configurations to meet such transition constraints is *NP*-complete for the well known languages of RCC-8, Interval Algebra, and Block Algebra. Based on this result, we also propose a framework where the temporal aspect of a sequence of qualitative spatial configurations is constrained by a Point Algebra network, and again show that the enhanced problem is in *NP* when considering the aforementioned languages. Our results lie within the area of Graph Traversal and allow for many practical and diverse applications, such as identifying optimal routes in mobile robot navigation, modelling changes of topology in biological processes, and computing sequences of segmentation steps used in image processing algorithms.

# 1 Introduction

*Time* and *space* are fundamental cognitive concepts that have been the focus of study in many scientific disciplines, including Artificial Intelligence and, in particular, Knowledge Representation. In this context, an emphasis has been made on qualitative spatiotemporal reasoning, which abstracts from numerical quantities of space and time using qualitative values instead (e.g., earlier, bigger, left of). The conciseness of the representational language used in the qualitative approach provides a promising framework that further boosts research and applications in spatiotemporal reasoning [11, 20].

In this paper, we focus on a particular spatiotemporal reasoning problem that lies within the area of Graph Traversal, which is one of the oldest areas of inquiry

<footnote n="1">¹ CRIL CNRS UMR 8188, Université d'Artois, Lens, France
{sioutis,condotta,salhi,mazure}@cril.fr</footnote>

<footnote n="2">² School of Dentistry, College of Medical and Dental Sciences, University of Birmingham, UK

d.a.randell@bham.ac.uk</footnote>

<footnote>*This work was funded by Université d'Artois and region Nord-Pas-de-Calais.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: Left: segmented cell bodies (green), lobulated cell nuclei (yellow and red) and background (black), Middle: segmented cell nucleus extending outside border of host cell (red pixels), Right: the result of applying a morphological erosion operator; here the original *partially overlaps* relation changes to *proper part*</figcaption></figure>

in Graph Theory. Graph Traversal commonly deals with visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way. We are interested in a problem related to the Hamiltonian path problem for a given graph, which is the graph traversal problem of finding a path in the graph that visits each vertex exactly once. Hamiltonian path related problems naturally extend into use cases where routes need to be ordered or optimised, minimising the traversal of paths and vertices already visited. This abstraction has many practical and diverse applications, from identifying optimal routes in mobile robot navigation, to modelling changes of topology in biological processes and computing sequences of segmentation steps used in image processing algorithms. All these application examples can be modelled as a sequence of successive states where we look for ways to order the states so that an assumed set of a priori constraints are satisfied. For example, in the case of a phagocyte ingesting food, one constraint may be that the food has to be part of a food vacuole in the animal before it can be digested and absorbed.

After introducing the general context of the problem we wish to study here, we specify our *problem of interest* as a Hamiltonian path related problem where we want to order a sequence of qualitative spatial configurations to meet certain transition constraints. This ordering is constrained by the use of conceptual neighbourhood graphs defined on qualitative spatial constraint languages. For this problem, we consider several well known qualitative spatial and temporal constraint languages, such as RCC-8 [13], Interval Algebra (IA) [1], Block Algebra (BA) [10], and Point Algebra (PA) [18, 3, 2]. In particular, PA encodes temporal relations between two points in the timeline, RCC-8 encodes topological relations between two regions that are non-empty regular subsets of some topological space, IA encodes relative position relations between intervals, and BA encodes relative position and containment relations between multi-dimensional objects.

We have already claimed that this abstraction has practical applications and now give a detailed example to better motivate the subject of our paper. In [14] the authors use a discrete version of the spatial logic RCC (from which the constraint language RCC-8 is derived) called DM (for Discrete Mereotopology)
to model the topological organization of segmented cells and their parts and
cellular structure in tissue. The domain model assumes an a priori constraint
that cell nuclei form parts of their host cells, however in the example shown
in Figure 1 the RCC-8 relation returned is *partially overlaps* and not *proper
part*. There are several reasons why this scenario may happen in practice, e.g.,
if the regions initially segmented out as cell nuclei are being over-segmented, or
variations in the histological stain density results in a less than optimal threshold
level being selected. The result means the labelled regions extracted from the
image cannot be a model. The task then is to repair the segmentation to restore
consistency and/or optimise the sequence of segmentation steps needed. As such,
a conceptual neighbourhood graph for DM is used to encode legal topological
transitions, and successive states from a start to end state are generated, and
then optimised. Paths through the network are then cashed out as a series of
image processing segmentation steps. A single histological image may have many
hundreds of cells, and the generation of symbolic models may or may not be
realised in an actual image. Moreover, some segmentation operations on regions
will reduce their size and may fragment a region into sub-parts, or separated
regions that increase their size may merge, so the computational task of finding
an optimal segmentation model can easily grow in complexity.

Two closely related contributions that deal with sequences of qualitative spa-
tial or temporal configurations consist of the works of Westphal et al. in [19] and
Cui et al. in [5]. In both of these papers, qualitative configurations extracted
follow a predefined ordering; where all pairs of consecutive qualitative configura-
tions in the sequence produced, meet certain transition constraints with respect
to an assumed conceptual neighbourhood graph. In our case, our knowledge
base already comprises a set of qualitative configurations, and the problem is
that of finding an ordering of those qualitative configurations when positioned
in a sequence, such that all the pairs of consecutive qualitative configurations
in the ordered sequence meet the aforementioned transition constraints. Thus,
we define a novel problem in the context of qualitative spatiotemporal reason-
ing, whose computational properties we are the first to study. In particular, we
make the following contributions: (i) we consider a sequence of qualitative spa-
tial configurations of RCC-8, IA, or BA, and show that it is NPN-complete to
order the configurations in a way such that the transition constraints are met
with respect to the conceptual neighbourhood graph of the considered language,
and (ii) we introduce a framework where the temporal aspect of a sequence
of qualitative spatial configurations of RCC-8, IA, or BA is replaced with a PA
network which further restricts the desired ordering of the configurations, but
which, nevertheless, allows the problem of finding such an ordering to be in NPN.

The paper is organized as follows. In Section 2 we introduce the notions of a qualitative constraint language, a qualitative constraint network, and a conceptual neighbourhood graph. Section 3 is our main section where we introduce the notions of a qualitative spatiotemporal sequence and a transition graph which encodes certain transition constraints, but also define our main problem, that of obtaining a desired ordering of the configurations in a given sequence, and pro-
<figure><img src="image_3.png" /><figcaption>Fig. 2: 2-dimensional examples of the base relations of RCC-8</figcaption></figure>

vide complexity results for different variations of it. In Section 4 we go one step further and introduce Point Algebra networks in our qualitative spatiotemporal sequences, thus, providing a new spatiotemporal framework. Finally, in Section 5 we conclude and discuss future work.

## 2 Qualitative Constraint Networks and Conceptual Neighbourhood Graphs

A (binary) qualitative temporal or spatial constraint language [15] is based on a finite set B of jointly exhaustive and pairwise disjoint (JEPD) relations defined on a domain D, called the set of base relations. The base relations of set B of a particular qualitative constraint language can be used to represent the definite knowledge between any two entities with respect to the given level of granularity. B contains the identity relation $Id$, and is closed under the converse operation ($^{-1}$). Indefinite knowledge can be specified by unions of possible base relations, and is represented by the set containing them. Hence, $2^B$ represents the total set of relations. $2^B$ is equipped with the usual set-theoretic operations union and intersection, the converse operation, and the weak composition operation denoted by symbol $\diamond$ [15]. We note that the notion of a qualitative constraint language is not consistent in literature, an issue which is nicely explained in the work of Dylla et al. in [6]. In this paper we consider a qualitative constraint language to be a relation algebra [6], which is the case for the most well known calculi such as RCC-8 [13], Interval Algebra (IA) [1], Block Algebra (BA) [10], and Point Algebra (PA) [18, 3, 2].

**Example 1.** As an example, the qualitative spatial constraint language RCC-8 [13] comprises the set of base relations {$DC$ (disconnected), $EC$ (externally connected), $PO$ (partially overlaps), $TPP$ (tangential proper part), $NTPP$ (non-tangential proper part), $TPPi$ (tangential proper part inverse), $NTPPi$ (non-tangential proper part inverse), $EQ$ (equals)}, with $EQ$ being the identity relation, as depicted in Figure 2.

Likewise, there exist other qualitative spatial constraint languages, such as the Interval Algebra (IA) [1] and the Block Algebra (BA) [10], with their own sets of base relations. Further, the qualitative temporal constraint language of Point Algebra (PA) [18, 3, 2] comprises the set of base relations {$<, =, >$}, with $=$ being the identity relation, where the relation symbols display the natural interpretation over time points in $Q$.
<figure><img src="image_4.png" /><figcaption>Fig. 3: A RCC-8 configuration (left) along with its QCN describing it (right)</figcaption></figure>

In what follows, if $\mathcal{L}$ is a qualitative constraint language, we will denote by $B_{\mathcal{L}}$ its set of base relations. Qualitative temporal or spatial constraint configurations can be formulated as qualitative constraint networks (QCNs) as follows:

**Definition 1.** Given a qualitative constraint language $\mathcal{L}$, a QCN $\mathcal{N}$ of $\mathcal{L}$ is a pair $(V, C)$ where: $V$ is a non-empty finite set of variables; $C$ is a mapping that associates a relation $C(v, v') \in 2^{\mathcal{B}_{\mathcal{L}}}$ to each pair $(v, v')$ of $V \times V$. $C$ is such that $C(v, v) = \{\text{Id}\}$ and $C(v, v') = (C(v', v))^{-1}$.

An example of a QCN of RCC-8 is depicted in Figure 3. Note that we always regard a QCN as a complete network. In what follows, given a QCN $\mathcal{N} = (V, C)$ and $v, v' \in V$, $\mathcal{N}[v, v']$ will denote the relation $C(v, v')$. Given a QCN $\mathcal{N} = (V, C)$ defined in some qualitative constraint language $\mathcal{L}$, we have the following definitions: $\mathcal{N}$ is said to be trivially inconsistent iff $\exists v, v' \in V$ with $\mathcal{N}[v, v'] = \emptyset$. A solution of $\mathcal{N}$ is a mapping $\sigma$ defined from $V$ to the domain $D$, yielding a spatial configuration, such that for every pair $(v, v')$ of variables in $V$, $(\sigma(v), \sigma(v'))$ can be described by $\mathcal{N}[v, v']$, i.e., there exists a base relation $b \in \mathcal{N}[v, v']$ such that the base relation defined by $(\sigma(v), \sigma(v'))$ is $b$.

**Definition 2.** A QCN $\mathcal{N}$ is satisfiable *iff it admits a solution*.

A sub-QCN $\mathcal{N}'$ of $\mathcal{N}$, is a QCN $(V, C')$ such that $\mathcal{N}'[v, v'] \subseteq \mathcal{N}[v, v'] \ \forall v, v' \in V$. If $b$ is a base relation, then $\{b\}$ is a singleton relation. An atomic QCN is a QCN where each constraint is a singleton relation. Given a solution $\sigma$ of $\mathcal{N}$, a scenario $\mathcal{N}(\sigma)$ of $\mathcal{N}$ is an atomic satisfiable sub-QCN of $\mathcal{N}$, such that $\forall v, v' \in V, \mathcal{N}(\sigma)[v, v']$ is defined by the base relation defined by $(\sigma(v), \sigma(v'))$. A subclass of relations is a set $A \subseteq 2^{\mathcal{B}_{\mathcal{L}}}$ closed under converse, intersection, and weak composition. In what follows, all the considered subclasses will contain the singleton relations and the universal relation $B_{\mathcal{L}}$ of $2^{\mathcal{B}_{\mathcal{L}}}$.

**Definition 3.** Given a qualitative constraint language $\mathcal{L}$, a subclass $A \subseteq 2^{\mathcal{B}_{\mathcal{L}}}$ is a tractable subclass if the satisfiability problem for a QCN $\mathcal{N}$ of $\mathcal{L}$ comprising only relations from $A$ is tractable. A subclass $A \subseteq 2^{\mathcal{B}_{\mathcal{L}}}$ is a maximal tractable subclass if there is no other tractable subclass that properly contains $A$.

A QCN $\mathcal{N}$ is ◇-consistent or closed under weak composition iff $\forall v, v', v'' \in V$ we have that $\mathcal{N}[v, v'] \subseteq \mathcal{N}[v, v''] \diamond \mathcal{N}[v'', v']$. Given a QCN $\mathcal{N} = (V, C)$, ◇-consistency can be applied in $O(|V|^3)$ time [15]. The constraint graph of a QCN $\mathcal{N} = (V, C)$ is the graph $(V, E)$, denoted by $G(\mathcal{N})$, for which we have that $(v, v') \in E$ iff $\mathcal{N}[v, v'] \neq B$.
Checking the satisfiability of a QCN is $\mathcal{NP}$-complete in general for the most well known calculi such as RCC-8, IA, and BA. However, there exist maximal tractable subclasses for those calculi for which the satisfiability problem for not trivially inconsistent and ◦-consistent QCNs comprising relations only from one of those subclasses becomes tractable, as noted earlier. For example, the maximal tractable subclasses for RCC-8 are the classes $\mathcal{H}_8$, $C_8$, and $Q_8$ [16]. For other calculi, their whole class of relations is tractable, as is the case with PA, i.e., $2^{\mathcal{B}_{PA}}$ is the maximal tractable subclass of PA. Regarding PA in particular, checking the satisfiability of a QCN of PA can be done in $O(|V|^2)$ time with a dedicated algorithm presented in [2, chap. 3]. However, ◦-consistency, as a more general approach, is still suitable for deciding the satisfiability of a QCN of PA.

The notion of conceptually neighbouring relations in some qualitative con-
straint language is strongly related to the continuity and proximity that these
relations might exhibit. In particular, we recall the following definition from [8]:

**Definition 4 ([8]).** Given a qualitative constraint language $\mathcal{L}$, we have that two base relations $b(u, v)$ and $b'(u, v)$, with $b, b' \in \mathcal{B}_{\mathcal{L}}$ and $u, v$ being two entities, are conceptual neighbours if they are proximal and can be directly transformed into one another by continuous deformation (e.g., in shape, size, or position) of entities $u$ and $v$.

*Example 2.* As an example, in RCC-8 the base relations *DC*(x, y) and *EC*(x, y) are conceptual neighbours since a continuous movement of the spatial entity x towards spatial entity y may cause a direct transition from relation *DC*(x, y) to relation *EC*(x, y). The relations *DC*(x, y) and *PO*(x, y) are not conceptual neighbours since a transition between those relations must go through relation *EC*(x, y). Another example in IA considers relations *m*(x, y) (meets) and *o*(x, y) (overlaps). These relations are conceptual neighbours since an entity can directly overlap another entity after having met it first.

Clearly, by Definition 4 it follows that every base relation is a conceptual
neighbour of itself, however, we do not depict any loops in our graphs to follow
for simplicity.

Conceptually neighbouring relations in any given qualitative constraint lan-
guage $\mathcal{L}$ can be captured with a conceptual neighbourhood graph, which is de-
fined as follows:

**Definition 5 ([8])<fnref n="3" />.** Given a qualitative constraint language $\mathcal{L}$, a conceptual neighbourhood graph of $\mathcal{L}$ is a graph $\Gamma = (\mathcal{B}_{\mathcal{L}}, E)$ where $E = \{(b(u, v), b'(u, v)) \mid b, b' \in \mathcal{B}_{\mathcal{L}} \text{ and } u, v \text{ being two entities; and } b(u, v) \text{ and } b'(u, v) \text{ being conceptual neighbours}\}$.

Conceptual neighbourhood graphs can be established for all qualitative con-
straint languages, a subset of which can be found in [8, 17, 7]. It is important

<footnote n="3">³Actually, Freska in [8] uses the term *neighbourhood structure* to describe what we formally define here as a graph.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 4: A conceptual neighbourhood graph of RCC-8</figcaption></figure>

to note that conceptual neighbourhood graphs are not unique for every qualitative constraint language as they can be subject to further restrictions, such as constraints subject to user preference, or restrictions on deformation.

*Example 3.* As an example, the conceptual neighbourhood graph of RCC-8 is depicted in Figure 4. The dashed edges represent transitions of base relations that are not allowed if we require that regions do not change size.

## 3 Qualitative Spatio-Temporal Sequences and Transition Graphs

In general, a spatial QCN, as described in Section 2, constitutes a static spatial configuration in some domain, over a set of spatial entities. To be able to describe a spatial configuration that changes over time, we can define the notion of a qualitative spatiotemporal sequence, which is nothing more than a sequence of spatial QCNs. The ordering of the QCNs in the aforementioned sequence constitutes a timeline that allows us to view how a spatial configuration evolves over time. We can define a qualitative spatiotemporal sequence (QSS) as follows:

**Definition 6.** Given a qualitative constraint language $\mathcal{L}$, a QSS $S$ of $\mathcal{L}$ is a sequence $(N_1 = (V, C_1), N_2 = (V, C_2), \dots, N_k = (V, C_k))$ of $k$ QCNs of $\mathcal{L}$ over a set of $n$ variables $V$, for some integers $k$ and $n$.

An atomic QSS is a QSS that comprises only atomic QCNs. Further, a solution and a scenario of a QSS is the sequence of solutions and scenarios of all its QCNs respectively.

**Definition 7.** A QSS $S$ is satisfiable *iff* it admits a solution.

In what follows, we will be interested in studying atomic QSSs, as the results obtained for that case can be carried to the general case of QSSs as well.

*Example 4.* An example of a spatiotemporal sequence based on RCC-8 is given in Figure 5. Figure 5 depicts the sequence $(N_a = (V, C_a), N_b = (V, C_b), N_c =$
<figure><img src="image_6.png" /><figcaption>Fig. 5: Example of a spatiotemporal sequence based on RCC-8</figcaption></figure>

(V, C_c), N_d = (V, C_d), N_e = (V, C_e), N_f = (V, C_f)), where V = {x, y, z} and N_a, N_b, N_c, N_d, N_e, and N_f are RCC-8 configurations over V. In particular, N_a defines the set of constraints {DC(x, y), DC(y, z), DC(x, z)}, N_b defines the set of constraints {EC(x, y), DC(y, z), DC(x, z)}, N_c defines the set of constraints {EC(x, y), DC(x, z), EC(x, z)}, N_d defines the set of constraints {PO(x, y), DC(y, z), EC(x, z)}, N_e defines the set of constraints {TPPi(x, y), DC(y, z), EC(x, z)}, and finally N_f defines the set of constraints {NTPPi(x, y), DC(y, z), DC(x, z)}. Each spatial QCN in the sequence corresponds to a unique point of time in the timeline t. For example, spatial configuration N_c corresponds to the point of time t_c in the timeline t. Thus, the ordering of the spatial QCNs in a given sequence yields a spatiotemporal configuration that describes how a spatial configuration evolves over time.

At this point, we can extend the notion of conceptually neighbouring relations to the notion of conceptually neighbouring atomic QCNs as follows:

**Definition 8.** Given a qualitative constraint language $\mathcal{L}$ and a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, we have that two atomic QCNs $\mathcal{N} = (V, C)$ and $\mathcal{N}' = (V, C')$ of $\mathcal{L}$ are conceptual neighbours with respect to $\Gamma$ if $\forall u, v \in V$ we have that $b(u, v)$ and $b'(u, v)$ are conceptual neighbours with respect to $\Gamma$, where $b(u, v)$ and $b'(u, v)$ are the base relations defined by the singleton relations $C(u, v)$ and $C'(u, v)$ respectively.

Intuitively, two atomic QCNs are conceptual neighbours if they can transition from one another by simultaneous transformation of their base relations to conceptually neighbouring base relations. We can also give the following definition of a conceptual neighbourhood graph for a set of atomic QCNs, but to avoid any confusion with the conceptual neighbourhood graph of the base relations of a qualitative constraint language $\mathcal{L}$ we will refer to it as a transition graph<fnref n="4" />:

**Definition 9.** Given a qualitative constraint language $\mathcal{L}$, a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, and a satisfiable atomic QSS $S = (\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k)$ of $\mathcal{L}$, the transition graph of $S$ defined with respect to $\Gamma$ is the graph $M = (\{\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k\}, E)$ where $E = \{(\mathcal{N}_i, \mathcal{N}_j) | \mathcal{N}_i, \mathcal{N}_j \in \{\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k\}; \text{ and } \mathcal{N}_i \text{ and } \mathcal{N}_j \text{ being conceptual neighbours with respect to } \Gamma\}$.

<footnote n="4">⁴In fact, the reader can easily verify that in the case where we have the set of all possible atomic QCNs of $\mathcal{L}$ over exactly two spatial entities, the transition graph defined by those QCNs corresponds to the conceptual neighbourhood graph of $\mathcal{L}$.</footnote>
<figure><img src="image_7.png" /><figcaption>Fig. 6: Transition graph of a spatiotemporal sequence</figcaption></figure>

The transition graph of a satisfiable atomic QSS $\mathcal{S}$ of $k$ QCNs encodes all the conceptually allowed transitions between its spatial QCNs, i.e., it encodes all the pairs of atomic QCNs that are conceptual neighbours with respect to an assumed conceptual neighbourhood graph. Clearly, if the QCNs are defined over a set of variables $V$, it takes $O(|V|^2)$ time to calculate if a transition is possible between the QCNs of a given pair of QCNs. As the transition graph of $\mathcal{S}$ has $k$ nodes and, thus, $O(k^2)$ possible edges, i.e., pairs of QCNs, obtaining the entire transition graph can be done in polynomial time. It is also the case that every node, i.e., every QCN, in a transition graph is a conceptual neighbour of itself.

**Example 5.** As an example, the transition graph of the spatiotemporal sequence depicted in Figure 5, is shown in Figure 6. Indeed, we can have continuous transitions between the spatial QCNs in the pairs $(\mathcal{N}_a, \mathcal{N}_b)$, $(\mathcal{N}_b, \mathcal{N}_c)$, $(\mathcal{N}_c, \mathcal{N}_d)$, $(\mathcal{N}_d, \mathcal{N}_e)$, $(\mathcal{N}_e, \mathcal{N}_f)$ of consecutive QCNs in the sequence $(\mathcal{N}_a, \mathcal{N}_b, \mathcal{N}_c, \mathcal{N}_d, \mathcal{N}_e, \mathcal{N}_f)$, but also continuous transitions between spatial configurations $\mathcal{N}_a$ and $\mathcal{N}_c$ (i.e., the pair $(\mathcal{N}_a, \mathcal{N}_c)$), and $\mathcal{N}_b$ and $\mathcal{N}_d$ (i.e., the pair $(\mathcal{N}_b, \mathcal{N}_d)$).

Let us recall the definition of a Hamiltonian path.

**Definition 10 ([9]).** Given a graph $G$, a Hamiltonian path in $G$ is a path that visits each vertex $v \in V(G)$ exactly once.

It is easy to see that the pairs of consecutive QCNs in the aforementioned sequence of Example 5 correspond to a Hamiltonian path illustrated with dashed arrows in Figure 6. Based on this observation, we will now formally introduce the main problem that we are interested in studying in this paper and sketch its relation with the problem of finding a Hamiltonian path in a given graph, which is known to be $\mathcal{NP}$-complete [9]. In fact, we will make a polynomial-time reduction of the Hamiltonian path problem to our problem. We call our problem the sequence ordering problem (SOP) and define it as follows:

**Definition 11.** Given a qualitative constraint language $\mathcal{L}$, a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, and a satisfiable atomic QSS $S = (\mathcal{N}_1, \mathcal{N}_2, ..., \mathcal{N}_k)$ of $\mathcal{L}$, the SOP for $S$ is the problem of obtaining an ordered sequence of the QCNs of $S$ such that the spatial QCNs $\mathcal{N}_i$ and $\mathcal{N}_j$ in every pair of consecutive QCNs $(\mathcal{N}_i, \mathcal{N}_j)$ in the ordered sequence are conceptual neighbours with respect to $\Gamma$.

The relation between the Hamiltonian path problem and the SOP is as follows:
<figure><img src="image_8.png" /><figcaption>Fig. 7: A conceptual neighbourhood graph</figcaption></figure>

**Lemma 1.** Given a qualitative constraint language $\mathcal{L}$, a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, a satisfiable atomic QSS $S$ of $\mathcal{L}$, and the transition graph $M$ of $S$ defined with respect to $\Gamma$, solving the SOP for $S$ is equivalent to obtaining a Hamiltonian path in $M$.

Indeed, as Lemma 1 suggests, a Hamiltonian path in the transition graph of a given qualitative spatiotemporal sequence, will provide us with an ordered sequence of its QCNs such that the QCNs in every pair of consecutive QCNs in the ordered sequence are conceptual neighbours with respect to some conceptual neighbourhood graph, and vice versa, as explained earlier in light of Example 5. We provide a definition on graph isomorphism that will be of use in what follows.

**Definition 12.** A graph $G_1 = (V_1, E_1)$ is isomorphic to a graph $G_2 = (V_2, E_2)$ iff there is a bijection $f: V_1 \to V_2$ such that $(u, v) \in E_1$ iff $(f(u), f(v)) \in E_2$.

It might be tempting at this point to suggest that the SOP for a given QSS $S$ is $\mathcal{NP}$-complete, as is the case with the Hamiltonian path problem. However, we first need to show that any arbitrary graph $G$ can be translated to an isomorphic to $G$ transition graph $M$ in polynomial time. This is a necessary requirement in our line of reasoning for proving $\mathcal{NP}$-completeness for the SOP, as it could be the case that for a given qualitative constraint language and its conceptual neighbourhood graph, the family of transition graphs that can be constructed allow for obtaining a Hamiltonian path in polynomial time. A trivial case, for example, would be knowing for a fact that any transition graph is a complete graph. Further, to be able to prove $\mathcal{NP}$-completeness for the SOP, we require that a qualitative constraint language has the $P_3$ property, defined as follows:

*Property 1 (Property $P_3$).* A qualitative constraint language $\mathcal{L}$ will be said to have the $P_3$ property if it satisfies the following conditions:

- $B_{\mathcal{L}}$ consists of at least three base relations $b_1, b_2$, and $b_3$;

- The conceptual neighbourhood graph defined by base relations $b_1, b_2$, and $b_3$ is the graph $\Gamma = (\{b_1(u, v), b_2(u, v), b_3(u, v)\}, \{(b_1(u, v), b_2(u, v)), (b_2(u, v), b_3(u, v))\})$, with $u$ and $v$ being two entities, as shown in Figure 7 (omitting loops);

- Base relation $b_1$ belongs to all the possible weak compositions among base relations $b_1, b_2$, and $b_3$, viz., $b_1 \in b_i \diamond b_j \forall i, j \in \{1, 2, 3\}$;

- The satisfiability of an atomic QCN defined by base relations $b_1, b_2$, and $b_3$ can be decided by $\diamond$-consistency.

By considering the base relations DC (disconnected), EC (externally connected), and PO (partially overlaps) for RCC-8 [13], the base relations $<$ (before), $m$ (meets), and $o$ (overlaps) for IA [1], and the base relations $<$ (left of), $\le$ (attached to), and $\Leftarrow$ (overlapping) for BA [10], we can obtain the following proposition:
V and a QCN in the set of $k$ QCNs of $\mathcal{L}$. This bijection is defined by a dictionary
map that given a node $v \in V$ returns the index $i$ of a QCN $\mathcal{N}_i$ in the set of $k$
QCNs of $\mathcal{L}$, i.e., $i = \text{map}[v]$, with $i \in \{1, 2, \dots, k\}$. For every $i \in \{1, 2, \dots, k\}$,
we have that every QCN $\mathcal{N}_i$ shares the set of variables $\{v_1, v_2, \dots, v_{k+1}\}$, viz.,
all $k$ QCNs of $\mathcal{L}$ are defined over the same set of variables $\{v_1, v_2, \dots, v_{k+1}\}$.
We assume first that $G$ is an edgeless graph, therefore, the $k$ QCNs of $\mathcal{L}$ are
initially constructed in a manner such that there exists no pair of QCNs where
the QCNs in the pair are conceptual neighbours of one another. This is achieved
by initializing relation $\mathcal{N}_i[v_i, v_{i+1}]$ for every QCN $\mathcal{N}_i$ with the singleton relation
$\{b_3\}$ while initializing all other relations $\mathcal{N}_i[v_j, v_o]$ with $i \neq j$ and $j < o$ with the
singleton relation $\{b_1\}$. Then, for any pair of QCNs $(\mathcal{N}_i, \mathcal{N}_j)$ from our set of $k$
QCNs of $\mathcal{L}$, we have that $\mathcal{N}_i$ and $\mathcal{N}_j$ are not conceptual neighbours, since the base
relations $b_3$ and $b_1$ defined by relations $\mathcal{N}_i[v_i, v_{i+1}]$ and $\mathcal{N}_j[v_i, v_{i+1}]$ respectively
(and equivalently, the base relations $b_1$ and $b_3$ defined by relations $\mathcal{N}_i[v_j, v_{j+1}]$
and $\mathcal{N}_j[v_j, v_{j+1}]$ respectively) are not conceptual neighbours. Up to this point
it should be clear that we have constructed a set of atomic QCNs that yield a
transition graph which is isomorphic to an edgeless graph of order $k$. Since every
QCN in our set of $k$ QCNs of $\mathcal{L}$ is defined over $k+1$ entities, and assuming that we
use a matrix to represent a given QCN, the construction of our QCNs is achieved
in $O(k^3)$ time. Now, we need to iterate the set of edges of graph $G$ and change
the QCNs in the corresponding pairs of QCNs into being conceptual neighbours
of one another. Using dictionary map, we obtain a pair of QCNs $(\mathcal{N}_i, \mathcal{N}_j)$ for
every edge $(u, u') \in E$, where $i = \text{map}[u]$ and $j = \text{map}[u']$. As noted earlier, $\mathcal{N}_i$
and $\mathcal{N}_j$ are not conceptual neighbours, since the base relations $b_3$ and $b_1$ defined
by relations $\mathcal{N}_i[v_i, v_{i+1}]$ and $\mathcal{N}_j[v_i, v_{i+1}]$ respectively (and equivalently, the base
relations $b_1$ and $b_3$ defined by relations $\mathcal{N}_i[v_j, v_{j+1}]$ and $\mathcal{N}_j[v_j, v_{j+1}]$ respectively)
are not conceptual neighbours. Therefore, we need to change the aforementioned
base relations $b_1$ into being base relation $b_2$, so that we can achieve conceptual
proximity with base relation $b_3$. In particular, we set relations $\mathcal{N}_j[v_i, v_{i+1}]$ and
$\mathcal{N}_i[v_j, v_{j+1}]$ to $\{b_2\}$ from $\{b_1\}$. Note that QCNs $\mathcal{N}_i$ and $\mathcal{N}_j$ become conceptual
neighbours only of one another, as any other QCN $\mathcal{N}_o$ with $i \neq o \neq j$ is not a
conceptual neighbour to either $\mathcal{N}_i$ or $\mathcal{N}_j$, since relation $\mathcal{N}_o[v_o, v_{o+1}]$ is defined
by $b_3$, and relations $\mathcal{N}_i[v_o, v_{o+1}]$ and $\mathcal{N}_j[v_o, v_{o+1}]$ are still defined by $b_1$ (and
equivalently, relations $\mathcal{N}_o[v_i, v_{i+1}]$ and $\mathcal{N}_o[v_j, v_{j+1}]$ are defined by $b_1$, and rela-
tions $\mathcal{N}_i[v_i, v_{i+1}]$ and $\mathcal{N}_j[v_j, v_{j+1}]$ are defined by $b_3$). After iterating the whole
set of edges of graph $G$, we will have that any two nodes $u$ and $u'$ of $G$ are
adjacent in $G$ if and only if $\mathcal{N}_{\text{map}[u]}$ and $\mathcal{N}_{\text{map}[u']}$ are adjacent in the transition
graph that is defined by the set $\{\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k\}$ of $k$ QCNs of $\mathcal{L}$. Formally,
if $M$ is the transition graph defined by the set $\{\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k\}$ of $k$ QCNs of
$\mathcal{L}$, we have that $(u, u') \in E(G)$ iff $(\mathcal{N}_{\text{map}[u]}, \mathcal{N}_{\text{map}[u']}) \in E(M)$. Thus, graph $M$ is
isomorphic to graph $G$. To fix the pairs of QCNs that are conceptual neighbours
and consequently introduce the edges in our transition graph, we require $O(k^2)$
time, as there can only be $O(k^2)$ edges in a $k$ order graph (and given that our
QCNs are represented by matrices we can alter their relations in $O(1)$ time). In
conclusion, algorithm Arachni requires $O(k^3)$ running time in total to process its
input and produce an output. Finally, we also need to show that every QCN in
the set of $k$ atomic QCNs of $\mathcal{L}$ that we have constructed is satisfiable. Due to our
construction, for every QCN $\mathcal{N}_i = (V_i, C_i)$, with $i \in \{1, 2, \dots, k\}$, we have that
every triple of variables $v_o, v_o'$ and $v_o''$ in $V_i$, with $o < o' < o''$, defines a set of
relations $\mathcal{N}_i[v_o, v_o']$, $\mathcal{N}_i[v_o', v_o'']$, and $\mathcal{N}_i[v_o, v_o'']$, such that $\mathcal{N}_i[v_o, v_o'']$ is always
defined by the base relation $b_1$, and $\mathcal{N}_i[v_o, v_o']$ and $\mathcal{N}_i[v_o', v_o'']$ are defined by
either of the three base relations $b_1, b_2$, and $b_3$. Due to the fact that $b_1 \in b_i \diamond b_j$
$\forall i, j \in \{1, 2, 3\}$, we have that $\mathcal{N}_i[v_o, v_o''] \subseteq \mathcal{N}_i[v_o, v_o'] \diamond \mathcal{N}_i[v_o', v_o'']$. Further, as
$\mathcal{L}$ is a relation algebra and therefore satisfies the axioms of $\diamond$-associativity, $^{-1}$-
involution, $^{-1}$-involutive distributivity, and Peircean law (sometimes called cycle
law) [6], we can decide that every path of length 2 in $\mathcal{N}_i$ is closed under the
weak composition operation defined by operator $\diamond$, thus, $\mathcal{N}_i$ is $\diamond$-consistent. As
$\diamond$-consistency decides the satisfiability of atomic QCNs of $\mathcal{L}$, we have that $\mathcal{N}_i$ is
a satisfiable QCN of $\mathcal{L}$ for every $i \in \{1, 2, \dots, k\}$. $\square$

We proceed with obtaining a complexity result for the SOP, for the case where
the considered satisfiable atomic QSS $S$ is defined over a qualitative constraint
language $\mathcal{L}$ satisfying property $P_3$.

**Theorem 1.** *The SOP for any satisfiable atomic QSS *S* of a qualitative constraint language *L* satisfying property *P*<sub>3</sub>, is *NP*-complete.*

*Proof.* *NP*-hardness follows from the fact that the Hamiltonian path problem is *NP*-complete, and we can translate any input of the Hamiltonian path problem, which is an arbitrary graph *G*, to an isomorphic to *G* transition graph *M* of some QSS *S* in polynomial time, due to Proposition 2. Further, due to the notion of isomorphism, it is clear that we can have a Hamiltonian path in *M* iff we can have a Hamiltonian path in *G*. By Lemma 1, we have that obtaining a Hamiltonian path in *M* is equivalent to solving the SOP for *S*, thus, we ultimately have obtained a polynomial-time reduction from the Hamiltonian path problem to the SOP. We can also explicitly define membership in *NP* due to the fact that provided with a candidate ordered satisfiable atomic QSS *S*, we can check if the QCNs in every pair of consecutive QCNs in *S* are conceptual neighbours in polynomial time. In particular, if *S* comprises *k* QCNs, we can only have *k* − 1 pairs of consecutive QCNs in the sequence, and we can check if the QCNs in a pair are conceptual neighbours in *O*(*n*<sup>2</sup>) time, given the fact than the QCNs are defined over *n* entities. (Note also that as suggested in the proof of Proposition 2, *n* can be equal to *k* + 1). Thus, the SOP for any satisfiable atomic QSS *S* of a qualitative constraint language *L* satisfying property *P*<sub>3</sub>, is *NP*-complete. □

Due to Proposition 1, we can immediately obtain the following result:

**Corollary 1.** *The SOP for any satisfiable atomic QSS *S* of RCC-8, IA, or BA, is *NP*-complete.*

We can obtain a variation of the SOP for a satisfiable atomic QSS *S*, where
we allow one to consider a number of up to *m* QCNs in addition to the number
of QCNs of $\mathcal{S}$ and solve the SOP for the new augmented QSS $\mathcal{S}'$. This is particularly useful if given a QSS $\mathcal{S}$ we are unable to solve the SOP for $\mathcal{S}$, because $\mathcal{S}$, for example, yields a disconnected transition graph and, thus, does not allow obtaining a Hamiltonian path in its transition graph. We provide a very simple, but, nevertheless, sufficient example to better explain this problem.

**Example 6.** Let RCC-8 be our qualitative constraint language of choice with its usual conceptual neighbourhood graph as depicted in Figure 4, and $(\mathcal{N}_a, \mathcal{N}_b,)$ a QSS $\mathcal{S}$ of RCC-8, where $\mathcal{N}_a$ defines the set of constraints $\{DC(x, y)\}$ and $\mathcal{N}_b$ defines the set of constraints $\{PO(x, y)\}$. Clearly, the transition graph of $\mathcal{S}$ is disconnected as $\mathcal{N}_a$ and $\mathcal{N}_b$ are not conceptual neighbours and, thus, there can be no transition from $\mathcal{N}_a$ to $\mathcal{N}_b$, and vice versa. In particular, the transition graph of $\mathcal{S}$ is the graph $M = (\{\mathcal{N}_a, \mathcal{N}_b\}, \emptyset)$. As such, the SOP for $\mathcal{S}$ is unsolvable, since there can be no Hamiltonian path in $M$. However, we can augment $\mathcal{S}$ with the QCN $\mathcal{N}_c$ that defines the set of constraints $\{EC(x, y)\}$, and obtain the QSS $\mathcal{S}' = (\mathcal{N}_a, \mathcal{N}_b, \mathcal{N}_c)$. Then, the transition graph of $\mathcal{S}'$ will be the graph $M' = (\{\mathcal{N}_a, \mathcal{N}_b, \mathcal{N}_c\}, \{(\mathcal{N}_a, \mathcal{N}_b), (\mathcal{N}_b, \mathcal{N}_c)\})$. The Hamiltonian path $(\mathcal{N}_a, \mathcal{N}_c, \mathcal{N}_b)$ in $M'$ is exactly a solution of the SOP for $\mathcal{S}'$, where we considered one extra QCN with respect to the number of QCNs of $\mathcal{S}$.

We call this new problem the *relaxed* sequence ordering problem (rSOP) and define it as follows:

**Definition 13.** Given an integer $m$, a qualitative constraint language $\mathcal{L}$, a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, and a satisfiable atomic QSS $\mathcal{S} = (\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k)$ of $\mathcal{L}$ over a set of variables $V$, the rSOP for $\mathcal{S}$ is the SOP for QSS $\mathcal{S}'$, where $\mathcal{S}'$ is the sequence $\mathcal{S}$ augmented with a set $\{\mathcal{N}'_1, \mathcal{N}'_2, \dots, \mathcal{N}'_n\}$ of $n$ QCNs of $\mathcal{L}$ over $V$, with $n \le m$.

We proceed with obtaining a complexity result for the rSOP, for the case where the considered satisfiable atomic QSS $\mathcal{S}$ is defined over a qualitative constraint language $\mathcal{L}$ satisfying property $P_3$.

**Theorem 2.** *The rSOP for any satisfiable atomic QSS $\mathcal{S}$ of a qualitative constraint language $\mathcal{L}$ satisfying property $P_3$ and some integer $m$, is $\mathcal{NP}$-complete.*

*Proof.* $\mathcal{NP}$-hardness follows from the fact that the SOP, which is $\mathcal{NP}$-complete due to Theorem 1, can be reduced to the rSOP in polynomial time, by just considering an integer value of $m=0$ for the rSOP. With the aforementioned requirement for integer $m$, it is clear that any input for the SOP serves as an input for the rSOP and a solution of the rSOP is also a solution of the SOP, and vice versa. Membership in $\mathcal{NP}$ follows from the fact that provided with a candidate ordered satisfiable atomic QSS $\mathcal{S}'$ which corresponds to an input satisfiable atomic QSS $\mathcal{S}$ augmented with $\le m$ QCNs, we can check if $\mathcal{S}'$ is a solution of the SOP for $\mathcal{S}'$ in polynomial time, as the SOP is in $\mathcal{NP}$. Also, we can check if $\mathcal{S}'$ contains $\le m$ more QCNs than $\mathcal{S}$ in linear time in the number of QCNs of $\mathcal{S}'$. Thus, the rSOP for any satisfiable atomic QSS $\mathcal{S}$ of a qualitative constraint language $\mathcal{L}$ satisfying property $P_3$ and some integer $m$, is $\mathcal{NP}$-complete. $\square$
Due to Proposition 1, we can immediately obtain the following result:

**Corollary 2.** The rSOP for any satisfiable atomic QSS $\mathcal{S}$ of RCC-8, IA, or BA and some integer $m$, is $\mathcal{NP}$-complete.

The rSOP, as is the case with the SOP, is a decision problem where we try to decide if an adequate ordered sequence exists, and if so, present that sequence as a solution of some input instance. However, we can also view the rSOP as an optimization problem [12, 4] where we try to minimize the integer value of $m$.

Before closing this section, let us introduce yet another problem that will be also useful for the next section in this paper. We can view the transition graph of a satisfiable atomic QSS as a digraph (also called a directed graph), where the edges, i.e., the pairs of QCNs, have a direction associated with them that specifies which QCN in the pair can transition to the other one. We call the corresponding problem the *directed* sequence ordering problem (dSOP) and define it as follows:

**Definition 14.** Given a qualitative constraint language $\mathcal{L}$, a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, a satisfiable atomic QSS $\mathcal{S} = (\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k)$ of $\mathcal{L}$, and a transition digraph $M_d = (\{\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k\}, A)$, with $A = (\{N_i, N_j\})$ and/or $(N_j, N_i) \mid (N_i, N_j) \in E)$, where $M = (\{\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k\}, E)$ is the transition graph of $\mathcal{S}$ defined with respect to $\Gamma$, the dSOP for $\mathcal{S}$ is the problem of obtaining an ordered sequence of the QCNs of $\mathcal{S}$ such that the spatial QCNs $N_i$ and $N_j$ in every pair of consecutive QCNs $(N_i, N_j)$ in the ordered sequence are conceptual neighbours with respect to $\Gamma$ and $(N_i, N_j) \in A$.

We proceed with obtaining a complexity result for the dSOP, for the case where the considered satisfiable atomic QSS $\mathcal{S}$ is defined over a qualitative constraint language $\mathcal{L}$ satisfying property $P_3$.

**Theorem 3.** The dSOP for any satisfiable atomic QSS $\mathcal{S}$ of a qualitative constraint language $\mathcal{L}$ satisfying property $P_3$, is $\mathcal{NP}$-complete.

*Proof.* $\mathcal{NP}$-hardness follows from the fact that the SOP, which is $\mathcal{NP}$-complete due to Theorem 1, can be reduced to the dSOP in polynomial time, by just considering a transition digraph $M_d = (V, A)$ of $\mathcal{S}$, with $A = (\{N_i, N_j\})$ and $(N_j, N_i) \mid (N_i, N_j) \in E)$, where $M = (V, E)$ is the transition graph of $\mathcal{S}$ defined with respect to $\Gamma$. Namely, for every edge in $M$ we introduce both directions of this edge, i.e., both arcs, in $M_d$. With the aforementioned requirement for the transition digraph $M_d$, it is clear that any input for the SOP serves as an input for the dSOP and a solution of the dSOP is also a solution of the SOP, and vice versa. Membership in $\mathcal{NP}$ follows from the fact that provided with a candidate ordered satisfiable atomic QSS $\mathcal{S}$, we need to check if $\mathcal{S}$ is a solution of the SOP for $\mathcal{S}$ and also check if the QCNs in every pair of $k-1$ pairs of consecutive QCNs in $\mathcal{S}$ form an arc that belongs to the transition digraph $M_d$. We can perform the former check in polynomial time as the SOP is in $\mathcal{NP}$. For the latter check, if we assume that we use a matrix to store the transition digraph $M_d$, we can check if a pair of QCNs forms an arc that belongs to the transition digraph $M_d$ in $O(1)$
time, thus, we need $O(k-1)$ time in total for all $k-1$ pairs of QCNs. As such, the dSOP for any satisfiable atomic QSS $\mathcal{S}$ of a qualitative constraint language $\mathcal{L}$ satisfying property $P_3$, is $\mathcal{NP}$-complete. $\square$

Due to Proposition 1, we can immediately obtain the following result:

**Corollary 3.** *The dSOP for any satisfiable atomic QSS $\mathcal{S}$ of RCC-8, IA, or BA, is $\mathcal{NP}$-complete.*

# 4 Constraining Qualitative Spatio-Temporal Sequences with Point Algebra

In Section 3 we studied the problem of ordering a qualitative spatiotemporal sequence (QSS) of QCNs to meet certain transition constraints, i.e., we studied the problem of ordering the sequence in a manner such that the QCNs in every pair of consecutive QCNs in the sequence are conceptual neighbours. A QSS comprises strictly spatial QCNs, but the ordering of the sequence itself constitutes a timeline upon which the spatial QCNs are defined. Therefore, a QSS has an implicit temporal aspect as it describes an evolving spatiotemporal configuration in some timeline. In this section we make this temporal aspect explicit by defining a framework where the timeline is constrained by Point Algebra (PA) [17, 2, 2, 1] relations. We remind the reader, that PA comprises the set of base relations {<, =, >}, with = being the identity relation, where the relation symbols display the natural interpretation over time points in $\mathcal{Q}$. This makes the problem even more interesting as we have both constraints propagating from the spatial aspect to the temporal aspect and the other way around, and it also makes it more expressive as we will see in a later example.

We obtain a spatiotemporal framework by defining the concept of a qualitative spatiotemporal constraint network (QSCN) that builds on PA and allows plugging in any qualitative spatial constraint language, such as RCC-8, IA, and BA. Intuitively, a QSCN is a QCN of PA where the set of variables corresponds to a set of spatial QCNs. We formally define a QSCN as follows:

**Definition 15.** *Given a qualitative constraint language $\mathcal{L}$, a QSCN $\mathcal{N}$ of $\mathcal{L}$ is a QCN $(W, R)$ of PA, where $W$ is a set of variables $\{N_1 = (V, C_1), N_2 = (V, C_2), \dots, N_k = (V, C_k)\}$ of $k$ satisfiable atomic QCNs of $\mathcal{L}$ over a set of $n$ spatial entities $V$, and $R$ the usual constraint mapping in a QCN as defined in Definition 1.*

In what follows, given a QSCN $\mathcal{N} = (W, R)$ and $v, v' \in W$, $\mathcal{N}[v, v']$ will denote the relation $R(v, v')$. An atomic QSCN $\mathcal{N}$ is a QSCN whose underlying QCN of PA is atomic, and a scenario $\mathcal{N}(\sigma)$ of $\mathcal{N}$ is a scenario of its underlying QCN of PA, where $\sigma$ is a solution of that QCN.

**Definition 16.** Let $(N_1, N_2, \dots, N_k)$ be the QSS defined by an atomic QSCN $\mathcal{N} = (\{N_1, N_2, \dots, N_k\}, R)$, denoted by $S(\mathcal{N})$, $\Gamma$ a conceptual neighbourhood graph of $\mathcal{L}$, and $M = (\{N_1, N_2, \dots, N_k\}, E)$ the transition graph of $S(\mathcal{N})$ defined with respect to $\Gamma$. Then, $S(\mathcal{N})$ yields a transition digraph $(\{N_1, N_2, \dots, N_k\}, A)$, denoted by $M_d(\mathcal{N})$, where $\forall N_i, N_j \in \{N_1, N_2, \dots, N_k\}$ with $i \le j$:
$$ \text{— } (\mathcal{N}_i, \mathcal{N}_j) \in A \text{ and } (\mathcal{N}_j, \mathcal{N}_i) \in A, \text{ if } (\mathcal{N}_i, \mathcal{N}_j) \in E \text{ and } \mathcal{N}[\mathcal{N}_i, \mathcal{N}_j] = \{=\}; $$

$$ \text{— } (\mathcal{N}_i, \mathcal{N}_j) \in A, \text{ if } (\mathcal{N}_i, \mathcal{N}_j) \in E \text{ and } \mathcal{N}[\mathcal{N}_i, \mathcal{N}_j] = \{<\}; $$

$$ \text{— } (\mathcal{N}_j, \mathcal{N}_i) \in A, \text{ if } (\mathcal{N}_i, \mathcal{N}_j) \in E \text{ and } \mathcal{N}[\mathcal{N}_i, \mathcal{N}_j] = \{>\}. $$

Given a QSCN $\mathcal{N}$ defined in some qualitative constraint language $\mathcal{L}$ along with a conceptual neighbourhood graph $\Gamma$ of $\mathcal{L}$, a solution of $\mathcal{N}$ is a solution of the dSOP for $S(\mathcal{N}(\sigma))$ with respect to $M_d(\mathcal{N}(\sigma))$, where $\sigma$ is a solution of the underlying QCN of PA of $\mathcal{N}$ and $\mathcal{N}(\sigma)$ its corresponding scenario.

**Definition 17.** A QSCN $\mathcal{N}$ is satisfiable *iff it admits a solution*.

Given a QSCN $\mathcal{N}$, obtaining a solution $\sigma$ of its underlying QCN of PA and consequently a scenario $\mathcal{N}(\sigma)$ of that QCN, will provide us with an input for the dSOP. In particular, a scenario of the QCN of PA (i.e., an atomic satisfiable sub-QCN of the QCN of PA) constrains the timeline upon which the spatial QCNs of sequence $S(\mathcal{N}(\sigma))$ are defined, by encoding a particular transition digraph $M_d(\mathcal{N}(\sigma))$ of $S(\mathcal{N}(\sigma))$, as defined in Definition 16. (Of course, the transitions defined by the obtained transition digraph $M_d(\mathcal{N}(\sigma))$ can be even further restricted upon user preference, by considering an other transition digraph with some of the arcs of $M_d(\mathcal{N})$ removed.) In a sense, a QSCN allows us to describe numerous different transition digraphs, but also transitions that cannot be described by a single transition digraph alone, as we will see in the following simplest of examples.

*Example 7.* Let us consider the QSCN $\mathcal{N} = (W, R)$ of RCC-8, where $W = \{\mathcal{N}_a = (\{x, y\}, \{DC(x, y)\}), \mathcal{N}_b = (\{x, y\}, \{EC(x, y)\})\}$ and $R(\mathcal{N}_a, \mathcal{N}_b) = \{>\}, \{<\}$. Clearly, $\mathcal{N}$ has two scenarios defined by $R(\mathcal{N}_a, \mathcal{N}_b) = \{>\}$ and $R(\mathcal{N}_a, \mathcal{N}_b) = \{<\}$ respectively. Thus, $\mathcal{N}$ encodes two transition digraphs containing arcs $(\mathcal{N}_a, \mathcal{N}_b)$ and $(\mathcal{N}_b, \mathcal{N}_a)$ respectively, ultimately representing the knowledge that either $\mathcal{N}_a$ will transition to $\mathcal{N}_b$, or $\mathcal{N}_b$ will transition to $\mathcal{N}_a$. This dichotomic behavior cannot be represented by a single transition digraph alone, as any such digraph would either allow both transitions between a pair of QCNs, or a single transition of one QCN to the other one in the pair.

Let us consider all the aforementioned notions around a QSCN in conjunction with a qualitative spatiotemporal sequence of Block Algebra (BA) [10], as follows:

*Example 8.* In Figure 8 we can view a QSCN $\mathcal{N} = (W, R)$ of BA, where $W = \{\mathcal{N}_x, \mathcal{N}_y, \mathcal{N}_z\}$ and $R$ is defined by the set of constraints $R(\mathcal{N}_x, \mathcal{N}_y) = \{>\}, \{<\}$, $R(\mathcal{N}_y, \mathcal{N}_z) = \{>\}, \{<\}$, and $R(\mathcal{N}_x, \mathcal{N}_z) = \{?\}$, where ? is the common notation in literature for the universal relation $B_{PA}$. Every variable of the underlying QCN of PA of $\mathcal{N}$ corresponds to a spatial QCN. As noted, for the sake of our example, we can view these spatial configurations as QCNs of BA. All QCNs of BA share the same set of spatial variables $V$ as imposed by Definition 15, which in our case comprises the disks of the Moon and the Sun. In fact, our example describes the phenomenon of an eclipse. The QCN $\mathcal{N}_x$ of BA comprises the set of constraints $\{\Rightarrow (\text{Moon}, \text{Sun})\}$ (the disk of the Moon overlaps the disk of the Sun from right to left). The QCN $\mathcal{N}_y$ of BA comprises the set of constraints $\{\sqsubseteq (\text{Moon}, \text{Sun})\}$
<figure><img src="image_9.png" /><figcaption>Fig. 8: Example of a QSCN of Block Algebra</figcaption></figure>

(the disk of the Moon contains the disk of the Sun). Finally, the QCN $N_z$ of BA comprises the set of constraints $\{\Leftarrow (\text{Moon}, \text{Sun})\}$ (the disk of the Moon overlaps the disk of the Sun from left to right). Assuming that two observers in different hemispheres can actually see the same eclipse event, we may want to be able to capture the phenomenon both as seen from the perspective of an observer in the Northern hemisphere (the Moon moves from right to left), but also as seen in the Southern hemisphere (the Moon moves from left to right). The reader can verify that both scenarios are encoded by the following possible solutions of $\mathcal{N}$: $(N_x, N_y, N_z)$ and $(N_z, N_y, N_x)$. In particular, solution $(N_x, N_y, N_z)$ corresponds to a scenario $\mathcal{N}(\sigma)$ of $\mathcal{N}$ defined by the set of constraints $R(N_x, N_y) = \{\Leftarrow\}, R(N_y, N_z) = \{\Leftarrow\}$, and $R(N_x, N_z) = \{\Leftarrow\}$, where $\sigma$ corresponds to a solution of the underlying QCN of PA such as $\sigma(N_x) = 0, \sigma(N_y) = 1$, and $\sigma(N_z) = 2$. Thus, solution $(N_x, N_y, N_z)$ of $\mathcal{N}$ is a solution of the dSOP for $S(\mathcal{N}(\sigma)) = (N_x, N_y, N_z)$ (where in this case we note that the input sequence is already ordered with respect to $M_d(\mathcal{N}(\sigma)))$. Regarding the transition digraph $M_d(\mathcal{N}(\sigma))$ of $S(\mathcal{N}(\sigma))$, it contains the arcs $(N_x, N_y)$ and $(N_y, N_z)$, as defined in Definition 16. The same line of reasoning holds for solution $(N_z, N_y, N_x)$.

We proceed with obtaining a complexity result for the satisfiability problem for a QSCN $\mathcal{N}$ of $\mathcal{L}$, as defined in Definition 17, for the case where $\mathcal{L}$ is qualitative constraint language satisfying property $P_3$.

**Theorem 4.** *The satisfiability problem for a QSCN $\mathcal{N}$ of $\mathcal{L}$, where $\mathcal{L}$ is qualitative constraint language satisfying property $P_3$, is NP-complete.*

*Proof.* $\mathcal{NP}$-hardness follows from the fact that the SOP, which is $\mathcal{NP}$-complete due to Theorem 1, can be reduced to the satisfiability problem for a QSCN in polynomial time. In particular, let $(N_1, N_2, \dots, N_k)$ be some QSS $\mathcal{S}$, then we can construct a QSCN $\mathcal{N} = (W, R)$ as follows. The set of variables $W$ will be the set $\{N_1, N_2, \dots, N_k\}$, and $R$ will be the mapping that associates the singleton relation $R(v, v') = \{=\}$ to each pair $(v, v')$ of $W \times W$, i.e., the underlying QCN of PA of $\mathcal{N}$ will be the atomic QCN of $|W|$ variables that is completely defined by singleton relation $\{=\}$. Assuming that we use a matrix to represent a given QCN, this construction can be made in $O(|W|^2)$ time, where $|W| = k$. The aforementioned underlying QCN of PA is obviously satisfiable, with a trivial solution being the mapping $\sigma$, where $\sigma(v) = 0 \ \forall v \in W$. Therefore, $\mathcal{N}(\sigma)$ is
exactly the underlying atomic QCN of PA, and is also a scenario of $\mathcal{N}$. As such, $\mathcal{N}(\sigma)$ will yield a QSS $S(\mathcal{N}(\sigma)) = (\mathcal{N}_1, \mathcal{N}_2, \dots, \mathcal{N}_k)$, and a transition digraph $M_d(\mathcal{N}(\sigma)) = (W, A)$ of $S(\mathcal{N}(\sigma))$, with $A = \{(\mathcal{N}_i, \mathcal{N}_j) \text{ and } (\mathcal{N}_j, \mathcal{N}_i) \mid (\mathcal{N}_i, \mathcal{N}_j) \in E\}$, where $M = (W, E)$ is the transition graph of $S$, as defined in Definition 16. Namely, for every edge in $M$ we introduce both directions of this edge, i.e., both arcs, in $M_d(\mathcal{N}(\sigma))$. Since $S = S(\mathcal{N}(\sigma))$, and for every edge $(u, v) \in E$ of $M$ we have both arcs $(u, v)$, $(v, u) \in A$ of $M_d(\mathcal{N}(\sigma))$, it is clear that any input for the SOP serves as an input for the dSOP and a solution of the dSOP is also a solution of the SOP, and vice versa. Finally, as a solution of a QSCN $\mathcal{N}$ is a solution of the dSOP for $S(\mathcal{N}(\sigma))$ with respect to $M_d(\mathcal{N}(\sigma))$, where $\sigma$ is a solution of the underlying QCN of PA of $\mathcal{N}$ and $\mathcal{N}(\sigma)$ its corresponding scenario, we ultimately have obtained a polynomial-time reduction from the SOP to the satisfiability problem for a QSCN. Membership in $\mathcal{NP}$ follows from the fact that provided with a candidate ordered satisfiable atomic QSS $S$, we need to check if $S$ is a solution of the dSOP for $S$ and also check if the QCN of PA that results by removing the forbidden relation $>$ from all relations $R(\mathcal{N}_i, \mathcal{N}_j)$ of the underlying QCN of PA of $\mathcal{N}$, where $\mathcal{N}_i$ and $\mathcal{N}_j$ constitute a pair of consecutive QCNs $(\mathcal{N}_i, \mathcal{N}_j)$ in $S$, is satisfiable. (If $R(\mathcal{N}_i, \mathcal{N}_j) = \{>\}$ in a scenario $\mathcal{N}(\sigma)$ of $\mathcal{N}$, we will obtain the arc $(\mathcal{N}_j, \mathcal{N}_i)$ in the corresponding transition digraph $M_d(\mathcal{N}(\sigma))$, which invalidates $S$ as a solution.) We can perform both checks in polynomial time as the dSOP is in $\mathcal{NP}$ due to Theorem 3, and $\diamond$-consistency decides the satisfiability of any QCN of PA (i.e., a scenario $\mathcal{N}(\sigma)$ of $\mathcal{N}$ along with solution $\sigma$ can be extracted in polynomial time). Thus, the satisfiability problem for a QSCN $\mathcal{N}$ of $\mathcal{L}$, where $\mathcal{L}$ is qualitative constraint language satisfying property $P_3$, is $\mathcal{NP}$-complete. $\square$

Due to Proposition 1, we can immediately obtain the following result:

**Corollary 4.** *The satisfiability problem for a QSCN $\mathcal{N}$ of RCC-8, IA, or BA, is $\mathcal{NP}$-complete.*

# 5 Conclusion and Future Work

In this paper, we investigated the task of ordering a temporal sequence of qualitative spatial configurations, where specific transition constraints with respect to a conceptual neighbourhood graph of a qualitative spatial constraint language are assumed. In particular, we showed that the problem of ordering a sequence of qualitative spatial configurations to meet such transition constraints is $\mathcal{NP}$-complete for the well known languages of RCC-8, Interval Algebra, and Block Algebra. We also proposed a framework where the temporal aspect of a sequence of qualitative spatial configurations is constrained by a Point Algebra network, and again showed that the enhanced reasoning task remains in $\mathcal{NP}$ when considering the aforementioned languages. As our results lie within the area of Graph Traversal, they allow for many practical and diverse applications, such as identifying optimal routes in mobile robot navigation, modelling changes of topology in biological processes, and computing sequences of segmentation steps used in
image processing algorithms. A direct consequence of our work would be to generalize to tree and graph structures to capture the temporal aspect of a set of qualitative spatial configurations.

## References

1. Allen, J.F.: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26, 832–843 (1983)

2. van Beek, P.: Reasoning About Qualitative Temporal Information. Artif. Intell. 58, 297–326 (1992)

3. van Beek, P., Cohen, R.: Exact and approximate reasoning about temporal relations. Computational Intelligence 6, 132–144 (1990)

4. Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (2001)

5. Cui, Z., Cohn, A.G., Randell, D.A.: Qualitative Simulation Based on a Logical Formalism of Space and Time. In: AAAI (1992)

6. Dylla, F., Mossakowski, T., Schneider, T., Wolter, D.: Algebraic Properties of Qualitative Spatio-temporal Calculi. In: COSIT (2013)

7. Egenhofer, M.J.: The Family of Conceptual Neighborhood Graphs for Region-Region Relations. In: GIScience (2010)

8. Freksa, C.: Conceptual neighborhood and its role in temporal and spatial reasoning. Decision Support Systems and Qualitative Reasoning pp. 181–187 (1991)

9. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)

10. Guesgen, H.W.: Spatial Reasoning Based on Allen's Temporal Logic. Tech. rep., International Computer Science Institute (1989)

11. Hazarika, S.: Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions. Igi Global (2012)

12. Krentel, M.W.: The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36, 490–509 (1988)

13. Randell, D.A., Cui, Z., Cohn, A.: A Spatial Logic Based on Regions and Connection. In: KR (1992)

14. Randell, D.A., Landini, G., Galton, A.: Discrete Mereotopology for Spatial Reasoning in Automated Histological Image Analysis. IEEE Trans. Pattern Anal. Mach. Intell. 35, 568–581 (2013)

15. Renz, J., Ligozat, G.: Weak Composition for Qualitative Spatial and Temporal Reasoning. In: CP (2005)

16. Renz, J., Nebel, B.: Efficient Methods for Qualitative Spatial Reasoning. JAIR 15, 289–318 (2001)

17. Santos, M.Y., Moreira, A.: Conceptual neighborhood graphs for topological spatial relations. In: WCE (2009)

18. Vilain, M., Kautz, H., van Beek, P.: Readings in qualitative reasoning about physical systems. chap. Constraint Propagation Algorithms for Temporal Reasoning: A Revised Report, pp. 373–381. Morgan Kaufmann Publishers Inc. (1990)

19. Westphal, M., Hué, J., Wölfli, S., Nebel, B.: Transition Constraints: A Study on the Computational Complexity of Qualitative Change. In: IJCAI (2013)

20. Wolter, F., Zakharyaschev, M.: Exploring artificial intelligence in the new millennium. chap. Qualitative Spatiotemporal Representation and Reasoning: A Computational Perspective. Morgan Kaufmann Publishers Inc. (2003)