On the Complexity of the Realisability Problem for Visit Events in Trajectory Sample Databases

To prove NP-hardness, we describe a reduction from SAT, the satisfiability problem of propositional formulas. Because the statement concerns query complexity, we reduce SAT to the $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-realisability problem with fixed sample and speed bound. In this case, we choose the sample $S=⟨((0,0),0),((0,0),1)⟩$ and the speed bound $v=1$. The input of the reduction is a propositional formula $\varphi$. We can assume that $\varphi$ is in negation normal form³³3A formula is said to be in negation normal form if negation operators are only applied to atoms., because the satisfiability problem remains NP-hard under this restriction. The output is a positive $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event $e_{\varphi }$ such that the formula $\varphi$ is satisfiable iff there exists a trajectory $\gamma$ in ${\mathrm{\Gamma }}_{(S,v)}$ that realises the event $e_{\varphi }$.

Let $P_1,\mathrm{\dots }{P}_k$ be the propositional symbols occuring in $\varphi$. For $1\le i\le k$, we define $t_i=\frac{i+1}{k+2}$, $p_i=(\frac{1}{2(k+2)},0)$ and $p_i^{\prime }=(-\frac{1}{2(k+2)},0)$. Now, we take $e_{\varphi }$ to be the result of substituting occurences of $\neg P_i$ by $\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(p_i^{\prime },t_i)$ and non-negated occurrences of $P_i$ by $\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(p_i,t_i)$ in $\varphi$. Clearly, $e_{\varphi }$ is a $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event, not containing negations.

Finally, we show that $\varphi$ is satisfiable if and only if there exists a $\gamma$ in ${\mathrm{\Gamma }}_{(S,v)}$ that realises $e_{\varphi }$. The “if”-direction is straightforward. If there is some $\gamma$ that realises $e_{\varphi }$, then $\varphi$ must certainly be satisfiable. To be precise, the assignment that assigns $P_i$ to true if and only if $\gamma (t_i)=p_i$ satisfies $\varphi$. For the “only if”-direction, assume that $\varphi$ is satisfiable. Then there exists a truth assignment $\alpha$ that makes $\varphi$ true. Now, we extend the sample $S$ to a sample $S^{\prime }$ such that it contains $(p_i,t_i)$ if $P_i$ is assigned true by $\alpha$, and otherwise contains $(p_i^{\prime },t_i)$. It is easily verified that $S^{\prime }$ is $v$-consistent, which means $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ is a $v$-bounded trajectory. Now, we have that $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ realises $\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(p_i,t_i)$ if $P_i$ is true under $\alpha$, and realises $\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(p_i^{\prime },t_i)$ if $\neg P_i$ is true under $\alpha$. It follows from the way we constructed the event, that $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ realises $e_{\varphi }$. $◀$

While the above result shows that the $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-realisability problem is NP-hard for positive events (not containing negations), the problem for $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖨𝗇𝗍𝖾𝗋𝗏𝖺𝗅})$-events already becomes NP-hard for conjunctions of atoms, as shown below.

We give a reduction from the Euclidean travelling saleman problem (E-TSP for short), shown to be NP-hard in [16] (the problem we refer to here is called the Euclidean tour-TSP there). The Euclidean travelling saleman problem asks, given a finite set of locations $P\subseteq {\mathbb{Q}}^2$ and a positive number $\mathrm{\ell }\in \mathbb{Q}$, whether there is a cycle through all locations of $P$ whose length is at most $\mathrm{\ell }$. Formally, this means there is a permutation $p_1,\mathrm{\dots },p_n$ of the locations in $P$ such that ${\sum }_{i=1}^{n-1}d(p_i,p_{i+1})+d(p_n,p_1)\le \mathrm{\ell }$. Without loss of generality, we assume that $P$ always contains the origin $(0,0)$.

Again, we work with a fixed sample $S=⟨((0,0),0)⟩$ and speed bound $v=1$. From an instance $P,\mathrm{\ell }$ of E-TSP, we give a conjunction of $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖨𝗇𝗍𝖾𝗋𝗏𝖺𝗅})$-atoms $C$, such that $(S,v)\vDash C$ if and only if there is cycle through $P$ of length at most $\mathrm{\ell }$. We define $C$ as

To prove that this reduction is correct, we first show that if $(S,v)\vDash C$, then there is cycle through $P$ of length at most $\mathrm{\ell }$. Let $\gamma$ be a $v$-bounded trajectory matching $S$ and realising $C$. Because $\gamma$ matches $S$, we have $\gamma (0)=(0,0)$. And, because $\gamma$ realises $C$, it reaches every location in $P$ at some moment in $[0,\mathrm{\ell }]$, and $\gamma (\mathrm{\ell })=(0,0)$. This induces an order $p_1,\mathrm{\dots },p_n$ of the locations in $P$, where $\gamma$ first reaches $p_1$, then $p_2$, and so on (we note that $p_1$ is always $(0,0)$). Thus, if we let $t_i$ be the first moment where $\gamma (t_i)=p_i$ for $i=1,\mathrm{\dots },n$, then . We claim the cycle $p_1,\mathrm{\dots },p_n,p_1$ has length at most $\mathrm{\ell }$. The length of this cycle is ${\sum }_{i=1}^{n-1}d(p_i,p_{i+1})+d(p_n,p_1)$. For every $i$, $\gamma$ visits $(p_i,t_i)$, and because $\gamma$ is $v$-bounded, we have $d(p_i,p_{i+1})\le v\cdot |t_i-t_{i+1}|=t_{i+1}-t_i$. Similarly, $\gamma$ visits $(p_n,t_n)$ and $(p_1,\mathrm{\ell })$, thus $d(p_n,p_1)\le \mathrm{\ell }-t_n$. It follows that the length of the cycle is at most ${\sum }_{i=1}^{n-1}(t_{i+1}-t_i)+\mathrm{\ell }-t_n=t_n-t_1+\mathrm{\ell }-t_n=\mathrm{\ell }$.

Finally, we show that if there is cycle through $P$ of length at most $\mathrm{\ell }$, then $(S,v)\vDash C$. Let $p_1,\mathrm{\dots },p_n,p_1$ be such cycle, where we choose $p_1$ to be $(0,0)$. Now, let $t_1=0$ and for $i=2,\mathrm{\dots },n$, take $t_i=t_{i-1}+d(p_{i-1},p_i)$. Then, $t_n={\sum }_{i=1}^{n-1}d(p_i,p_{i+1})$, which, by assumption, is at most $\mathrm{\ell }-d(p_n,p_1)$. Define the trajectory sample $S^{\prime }=⟨(p_1,t_1),\mathrm{\dots },(p_n,t_n),(p_1,\mathrm{\ell })⟩$. It is clear from the definition of $t_i$ that the part of $S^{\prime }$ excluding $(p_1,\mathrm{\ell })$ is $v$-consistent. We have seen that $t_n\le \mathrm{\ell }-d(p_n,p_1)$, and thus $d(p_n,p_1)\le \mathrm{\ell }-t_n$, which implies that $S^{\prime }$ is $v$-consistent. From this follows that $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ is $v$-bounded, and it clearly matches $S$ and realises $C$. $◀$

The “only if”-direction is obvious. We prove the “if”-direction. Assume (1), (2) and (3) are true. By (1), there exists a $v$-bounded trajectory ${\gamma }_0$ matching $⟨(p_1,t_1)⟩$ that realises $C_{(-\mathrm{\infty },t_1]}$. By (2), for $i=1,\mathrm{\dots },n-1$, there exists a $v$-bounded trajectory ${\gamma }_i$ matching $⟨(p_i,t_i),(p_{i+1},t_{i+1})⟩$ that realises $C_{[t_i,t_{i+1}]}$. And by (3), there exists a $v$-bounded trajectory ${\gamma }_n$ matching $⟨(p_n,t_n)⟩$ that realises $C_{[t_n,+\mathrm{\infty })}$. We define the trajectory $\gamma$ as follows:

We note that the intervals $[t_{i-1},t_i]$ and $[t_i,t_{i+1}]$ both contain $t_i$. However, this does not pose a problem for the definition of $\gamma$, because both ${\gamma }_{i-1}$ and ${\gamma }_i$ visit $(p_i,t_i)$, which means ${\gamma }_{i-1}(t_i)={\gamma }_i(t_i)=p_i$. It only requires a simple application of the triangle inequality (of Euclidean distance) to show that $\gamma$ is a $v$-bounded trajectory. For $i=1,\mathrm{\dots },n$, we have $\gamma (t_i)=p_i$, thus $\gamma$ matches $S$. The only thing left to prove is that $\gamma$ realises $C$. Let $A=\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(R,t)$ be an arbitrary conjunct of $C$. Depending on $t$, there are three cases to be considered. First, if $t\in (-\mathrm{\infty },t_1]$, then $A$ is a conjunct of $C_{(-\mathrm{\infty },t_1]}$. This implies ${\gamma }_0$ realises $A$, so $\gamma (t)={\gamma }_0(t)\in R$, which means $\gamma$ realises $A$. The other two cases, when $t$ is contained in $[t_i,t_{i+1}]$ or in $[t_n,+\mathrm{\infty })$, are similar. Because $\gamma$ realises all the conjuncts of $C$, it also realises $C$ itself. $◀$

We remark that we consider condition (2) from the lemma to be false when some space-time point among $(p_1,t_1),\mathrm{\dots }(p_k,t_k)$ shares its temporal component with a point in $S$, while their spatial component differs.

The “only if”-direction is obvious. We prove the “if”-direction. Assume there are locations $p_1,\mathrm{\dots },p_k$ satisfying (1) and (2). Now take the trajectory $\gamma$ to be the linear interpolation trajectory of the sample containing the points $(p_1,t_1),\mathrm{\dots },(p_k,t_k)$, as well as the ones in $S$. It is clear that $\gamma$ matches $S$ and assumption (2) implies it is a $v$-bounded trajectory. Finally, assumption (1) implies that $\gamma$ realises $C$. $◀$

The following proposition follows directly from the fact that, for $p\in {ℝ}^2$, we have $p\notin R(\phi )$ if and only if $p\in R(\neg \phi )$.

Given an arbitrary $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event, we can convert it into negation normal form and use Proposition 20 to remove all negations. The result of this process is a positive $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event that is equivalent to the original. Because this process can be performed in linear time (with respect to the length of the event), we can assume that any given $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event is positive, without loss of generality.

We describe an algorithm to decide the realisability problem of a $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event $e$ for input sample $S=⟨(p_1,t_1),\mathrm{\dots },(p_n,t_n)⟩$, where $p_i=(x_i,y_i)$, and speed bound $v$. Noting the remark made above, we assume that $e$ is positive. The first step is to convert $e$ into its disjunctive normal form $\overline{e}$. Since we are dealing with data complexity, the possibly increased size of $\overline{e}$, compared to $e$, has no impact on the running time of our method. In fact, because the number of disjuncts of $\overline{e}$ is constant, it is sufficient to show that the realisability problem for a single disjunct can be decided in linear time.

Consider a disjunct $C$ of $\overline{e}$. Because $\overline{e}$ is positive and in DNF, the event $C$ must be a conjunction of atomic events. This means we can apply Lemma 17, and we can determine whether $(S,v)\vDash C$ by testing whether each of the following conditions are met:

1. (1)

   $(⟨(p_1,t_1)⟩,v)\vDash C_{(-\mathrm{\infty },t_1]}$,

2. (2)

   for $i=1,\mathrm{\dots },n-1$, we have $(⟨(p_i,t_i),(p_{i+1},t_{i+1})⟩,v)\vDash C_{[t_i,t_{i+1}]}$, and

3. (3)

   $(⟨(p_n,t_n)⟩,v)\vDash C_{[t_n,+\mathrm{\infty })}$.

We focus our attention to condition (2). For every value of $i$, we want to decide whether $C_{[t_i,t_{i+1}]}$ is realisable for sample $⟨(p_i,t_i),(p_{i+1},t_{i+1})⟩$ and speed bound $v$. Let us write the conjunction $C_{[t_i,t_{i+1}]}$ as $\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(R({\phi }_1),t_1^{\prime })\wedge \mathrm{\cdots }\wedge \mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(R({\phi }_k),t_k^{\prime })$, with $t_1^{\prime }\le \mathrm{\cdots }\le t_k^{\prime }$. We remark that this implies $t_i\le t_1^{\prime }\le \mathrm{\cdots }\le t_k^{\prime }\le t_{i+1}$. From Lemma 18, we know that $(⟨(p_i,t_i),(p_{i+1},t_{i+1})⟩,v)\vDash C_{[t_i,t_{i+1}]}$ if and only if there exist locations $q_1,\mathrm{\dots },q_k\in {ℝ}^2$, with $q_i=(x_i^{\prime },y_i^{\prime })$, such that

1. (a)

   for $j=1,\mathrm{\dots },k$ we have $q_j\in R({\phi }_j)$, and

2. (b)

   the sample $⟨(p_i,t_i),(q_1,t_1^{\prime }),\mathrm{\dots },(q_k,t_k^{\prime }),(p_{i+1},t_{i+1})⟩$ is $v$-consistent.

In other words, we have $(⟨(p_i,t_i),(p_{i+1},t_{i+1})⟩,v)\vDash C_{[t_i,t_{i+1}]}$ if and only if the formula $\psi =\exists x_1^{\prime }\exists y_1^{\prime }\exists \mathrm{\dots }\exists x_k^{\prime }\exists y_k^{\prime }({\psi }_a\wedge {\psi }_b)$ is true, where ${\psi }_a$ is ${\phi }_1(x_1^{\prime },y_1^{\prime })\wedge \mathrm{\cdots }\wedge {\phi }_k(x_k^{\prime },y_k^{\prime })$, expressing condition (a), and to express condition (b), we take ${\psi }_b$ to be the conjunction of $k+1$ distance inequalities.

Because $\psi$ is a first-order logic sentence over the ordered field of real numbers, its truth can be determined by a decision procedure for the theory of real closed fields (first described by Tarski [19], we refer to Basu et al. [2] for a modern exposition). We note that the size of $\psi$ is independent of $n$, and thus has constant size in the data complexity setting ($k$ is bounded by the length of $C$). The time needed to determine the truth of $\psi$ is thus also constant. To test for condition (2), we have to perform the above steps for $n-1$ values of $i$. Conditions (1) and (3) can both be tested in constant time, in a manner similar to the above, the only difference is that the constructed sentence requires one less inequality for expressing $v$-consistency. We have thus shown that the realisability problem for a single disjunct of $\overline{e}$ can be answered in $O(n)$ time. This concludes the proof. $◀$

Our next result concerns the data complexity of the $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖨𝗇𝗍𝖾𝗋𝗏𝖺𝗅})$-realisability problem for positive events.

We first prove the “if”-direction. Assume that there exist $(p_1,t_1),\mathrm{\dots },(p_k,t_k)$ satisfying (1) and (2). Let $S^{\prime }$ be the sample containing the points $(p_1,t_1),\mathrm{\dots },(p_k,t_k)$, as well as the ones in $S$. Assumption (1) says $S^{\prime }$ is $v$-consistent, which means $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ is $v$-bounded. Because $S^{\prime }$ is an extension of $S$, and $\gamma$ matches $S^{\prime }$, it must also match $S$. The trajectory $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ realises all the atoms $A_i$ for which $(p_i,t_i)\in R_i\times T_i$, and potentially others. Because of assumption (2) and the fact that $e$ is positive, $\mathrm{𝖫𝖨𝖳}(S^{\prime })$ realises $e$, and thus $(S,v)\vDash e$.

For the “only if”-direction, we assume that $(S,v)\vDash e$. That means that there exists a $v$-bounded $\gamma$ realising $e$ and matching $S$. We choose $(p_1,t_1),\mathrm{\dots },(p_k,t_k)$ as follows. For every atom $A_i$ which $\gamma$ realises, we know that $\gamma$ visits some point in $R_i\times T_i$, and take $(p_i,t_i)$ to be such point. For an atom $A_i$ not realised by $\gamma$, we take (quite arbitrarily) $(p_i,t_i)$ to be the first anchor point of $S$. Then, $(p_i,t_i)\notin R_i\times T_i$, since otherwise $\gamma$ would realise $A_i$. All points of $(p_1,t_1),\mathrm{\dots },(p_k,t_k)$ and $S$ are visited by $\gamma$, so the sample containing all those points must be $v$-consistent, satisfying condition (1). Because $\gamma$ realises $A_i$ if and only if $(p_i,t_i)\in R_i\times T_i$ and $\gamma$ realises $e$, condition (2) is also satisfied. $◀$

The following proposition follows directly from the definition of $v$-consistency and the fact that the distance function $d$ obeys the triangle inequality.

It will be of interest later that the condition $d(p_1,p_2)\le v\cdot |t_1-t_2|$ from the above proposition is equivalent to $d{(p_1,p_2)}^2\le v^2\cdot {(t_1-t_2)}^2$, which, if $p_1=(x_1,y_1)$ and $p_2=(x_2,y_2)$, is a polynomial inequality with variables $x_1,y_1,t_1,x_2,y_2,,t_2,v$.

We describe an algorithm to decide the realisability of a positive $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖨𝗇𝗍𝖾𝗋𝗏𝖺𝗅})$-event $e$ for input sample $S$, of length $n$, and speed bound $v$. Lemma 22 gives a condition equivalent to $(S,v)\vDash e$. We can express this condition using a first-order logic sentence over the ordered field of real numbers $\psi =\exists x_1\exists y_1\exists t_1\mathrm{\dots }\exists x_k\exists y_k\exists t_k({\psi }_1\wedge {\psi }_2)$, where ${\psi }_1$ expresses part (1) of Lemma 22, and ${\psi }_2$ expresses part (2). To express part (1), stating that the sample containing $(x_1,y_1,t_1),\mathrm{\dots },(x_k,y_k,t_k)$ as well as the points from $S$ is $v$-consistent, we can take ${\psi }_1$ to be a conjunction of ${(n+k)}^2$ distance inequalities, as per Proposition 23. To express the second part, we construct ${\psi }_2$ by taking $e$ and replacing every atom $\mathrm{𝗏𝗂𝗌𝗂𝗍𝗌}(R({\phi }_i),[t_i^{-},t_i^{+}])$ by the formula ${\phi }_i(x_i,y_i)\wedge t_i^{-}\le t_i\wedge t_i\le t_i^{+}$.

We have now constructed a formula $\psi$ which is true if and only if $(S,v)\vDash e$. Thus, if there is a method to determine the truth $\psi$, we can decide the realisability problem for positive $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖨𝗇𝗍𝖾𝗋𝗏𝖺𝗅})$-events. Because $\psi$ is an existantial sentence, we can apply known decision procedures for the existential theory of the reals. Of course, the time complexity required to decide the realisability of positive $(\mathrm{𝖲𝖾𝗆𝗂𝖠𝗅𝗀},\mathrm{𝖨𝗇𝗍𝖾𝗋𝗏𝖺𝗅})$-events in the described manner, depends on the time complexity of the existential theory of the reals. In [2] (see theorem 13.14), an upper bound of $s^{m+1}{d}^{O(m)}$ is given, where $s$ is the number of polynomials occuring in the formula, $m$ the number of variables, and $d$ the maximum degree of the polynomials. Because we are considering data complexity, the number of polynomials in the ${\phi }_i$’s, as well as their maximum degree, is constant, and so is $k$. This implies that $\psi$ contains $O(n^2)$ polynomials of constant degree, and $3k$ variables. Thus, by Theorem 13.14 from [2], the truth of $\psi$ can be decided in $O({(n^2)}^{3k+1})=O(n^{6k+2})$ time, which is polynomial in $n$. It is also clear that $\psi$ can be constructed in polynomial time. $◀$

It is obvious that the conditions (1), (2) and (3) are necessary for the existence of a $v$-bounded trajectory matching $S_1$ and not visiting points in $S_2$. To show that they are also sufficient, we assume that all three conditions are met. Consider the trajectory $\mathrm{𝖫𝖨𝖳}(S_1)$. By condition (2), it is $v$-bounded. In case $\mathrm{𝖫𝖨𝖳}(S_1)$ visits one or more points from $S_2$, we show that we can extend (by adding points) $S_1$ to a sample $S^{\ast }$, such that $\mathrm{𝖫𝖨𝖳}(S^{\ast })$ is $v$-bounded, matches $S_1$ and does not visit points from $S_2$. Because $S^{\ast }$ is obtained by adding points to $S_1$, it is obvious that $\mathrm{𝖫𝖨𝖳}(S^{\ast })$ matches $S_1$. Let us say that $\mathrm{𝖫𝖨𝖳}(S_1)$ visits a point $(q,t)$ from $S_2$ on the line segment between $(p_i,t_i)$ and $(p_{i+1},t_{i+1})$. From (1) we know that , and from (3) we have . Together, these observations imply there must be a small disk around $q$, such that for every $p$ in this disk, the extension of $S_1$ with the point $(p,t)$ remains $v$-consistent. Informally, this means we can deviate $\mathrm{𝖫𝖨𝖳}(S_1)$ slightly between $t_i$ and $t_{i+1}$, while the trajectory remains $v$-bounded. Now, for every point $(q^{\prime },t^{\prime })$ of $S_2$ with , there is at most one choice for $p$ inside the disk that makes the linear interpolation trajectory of the extended sample visit $(q^{\prime },t^{\prime })$. Because there are infinitely many points in the disks, we can choose $p$ such that, between $t_i$ and $t_{i+1}$, none of the points from $S_2$ are visited. We can repeat this process for each line segment of $\mathrm{𝖫𝖨𝖳}(S_1)$ that visits a point from $S_2$. The linear interpolation trajectory of the resulting sample $S^{\ast }$ then matches $S_1$, is $v$-bounded and does not visit points from $S_2$, as desired. $◀$

We assume that we are given a conjunction $C$ of $k$ $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-literals, a sample $S$ of length $n$ and a speed bound $v$ as input. Let $P_1,\mathrm{\dots },P_m$ be the positive atoms occuring in $C$ and let $N_1,\mathrm{\dots },N_{\mathrm{\ell }}$ be the atoms occuring negated in $C$. First we compute the sample $S_1=⟨(p_1,t_1),\mathrm{\dots }(p_{n+m},t_{n+m})⟩$, containing both the points in $S$ and the ones occuring in the atoms $P_1,\mathrm{\dots },P_m$. Computing this sample requires ordering the points occuring in $P_1,\mathrm{\dots },P_m$ by time, and merging these with those from $S$ (which are already ordered by time). This can be done in $O(n+k\log k)$ time. We also compute a sample $S_2$, containing the points from $N_1,\mathrm{\dots },N_{\mathrm{\ell }}$, in $O(k\log k)$ time. Now we have $(S,v)\vDash C$ if and only if there exists a $v$-bounded trajectory matching $S_1$ and not visiting any point in $S_2$. This can be determined by testing for the conditions of Lemma 25 in $O(|S_1|+|S_2|)$ time, where $|S_1|+|S_2|=n+m+\mathrm{\ell }=n+k$. Thus, the total time required by the described procedure is $O(n+k\log k)$. $◀$

We assume that we are given a $(\mathrm{𝖯𝗈𝗂𝗇𝗍},\mathrm{𝖬𝗈𝗆𝖾𝗇𝗍})$-event $e$ in disjunctive normal form, of length $k$, a sample $S$ of length $n$ and a speed bound $v$ as input. Then, $e$ is of the form $C_1\vee \mathrm{\cdots }\vee C_{\mathrm{\ell }}$, where every disjunct $C_i$ is a conjunction of literals. Let us say that the event $C_i$ contains $k_i$ literals. Because $e$ is realisable if and only if one of the $C_i$’s is realisable, we can use Theorem 26 to determine the realisability of $e$, by determining it for each of the disjuncts. This takes ${\sum }_{i=1}^{\mathrm{\ell }}O(n+k_i\log k_i)$ time, which is $O(kn+k\log k)$. $◀$