The University of
Sydneyjoachim.gudmundsson@sydney.edu.auhttps://orcid.org/0000-0002-6778-7990
Funded by the Australian Government through the Australian Research Council
DP180102870. The University of
Sydneyzijin.huang@uni.sydney.edu.auhttps://orcid.org/0000-0003-3417-5303 The
University of
Sydneyandre.vanrenssen@sydney.edu.auhttps://orcid.org/0000-0002-9294-9947 The
University of
Sydneyswon7907@sydney.edu.auhttps://orcid.org/0000-0003-3803-3804

###### Acknowledgements.

The authors thank Kevin Buchin for the insightful discussion on the important
Lemma 5.1. The authors thank the anonymous reviewers for their helpful
feedback. Joachim Gudmundsson, Zijin Huang, André van Renssen and Sampson Wong
[10010063]Computational Geometry

# Computing a Subtrajectory Cluster from $c$-packed Trajectories

Joachim Gudmundsson  Zijin Huang  André van Renssen  Sampson Wong

(October 2022)

###### Abstract

We present a near-linear time approximation algorithm for the subtrajectory
cluster problem of $c$-packed trajectories. The problem involves finding $m$
subtrajectories within a given trajectory $T$ such that their Fréchet
distances are at most $(1+\varepsilon)d$, and at least one subtrajectory must
be of length $l$ or longer. A trajectory $T$ is $c$-packed if the intersection
of $T$ and any ball $B$ with radius $r$ is at most $c\cdot r$ in length.

Previous results by Gudmundsson and Wong [24] established an $\Omega(n^{3})$
lower bound unless the Strong Exponential Time Hypothesis fails, and they
presented an $O(n^{3}\log^{2}n)$ time algorithm. We circumvent this
conditional lower bound by studying subtrajectory cluster on $c$-packed
trajectories, resulting in an algorithm with an
$O((c^{2}n/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time
complexity.

###### keywords:

Subtrajectory cluster, $c$-packed trajectories, Computational geometry

##  1 Introduction

With the proliferation of location-aware devices comes an abundance of
trajectory data. One way to process and make sense of many trajectories is to
group long and similar subtrajectories. The analysis of long and similar parts
of trajectories can provide insights into behavior and mobility patterns, such
as common routes taken and places visited frequently.

Buchin et al. [8] initialised the study of subtrajectory cluster problems to
detect and extract common movement patterns. The Subtrajectory Cluster (SC)
decision problem is defined as follows. Given one or more trajectories,
determine if there exists a cluster of $m-1$ non-overlapping subtrajectories
and one reference trajectory. The reference trajectory $T_{r}$ must be at
least of length $l$, and the Fréchet distances between $T_{r}$ and the other
$m-1$ subtrajectories must be at most $d$. In the case of animals, long and
common movement patterns can indicate movement between grazing spots of sheep
or the migration flyway of seabirds. In the case of humans, common movement on
a Monday morning can show commuting patterns to find the most heavily
congested areas.

Subtrajectory clustering has attracted research from multiple communities.
Gudmundsson and Wolle [23] used subtrajectory cluster to analyse the common
movement patterns of football players. Buchin et al. [7] applied subtrajectory
cluster to map reconstruction by clustering common movement patterns of
vehicles into road segments. Researchers in the Geographical Information and
Data Mining communities also considered the variants and practical performance
of subtrajectory cluster algorithms [11, 30, 21, 22, 27, 1, 17]. In addition,
the potential of SC is examined in a wide range of applications, including
sports player analysis [31] and human movement analysis [10, 26].

Several theoretical studies of the subtrajectory clustering problem focus on
improving the quality of clustering. Agarwal et al. [1] defined a single
objective function, the weighted sum of three quality measures of a
clustering. These quality measures include the number of clusters chosen, the
quality of the cluster, and the size of the trajectories excluded from the
clustering. Brüning et al. [6] studied so-called $\triangle$-coverage, aiming
to find a set $C$ of curves to cover a polygonal curve such that a curve in
$C$ is fixed in size, and $|C|$ is minimised.

However, despite considerable attention from multiple communities, there is no
subcubic time algorithm that solves the subtrajectory cluster problem,
limiting its usefulness on large data sets. Buchin et al. [8] solved the
subtrajectory cluster problem in $O(n^{5})$ time when the similarity
measurement of two trajectories is the Fréchet distance, and Gudmundsson and
Wong [24] further improved the runtime with an $O(n^{3}\log^{2}n)$ time
algorithm. In addition, Gudmundsson and Wong [24] showed that there is no
$O(n^{3-\delta})$ algorithm for subtrajectory cluster for any $\delta>0$
unless the Strong Exponential Time Hypothesis (SETH) fails.

SC is unlikely to have a strongly subquadratic algorithm even if we allow a
small approximation factor on the Fréchet distances between subtrajectories.
Because given two trajectories $T_{1}$ and $T_{2}$, we can structure the SC
problem to find two subtrajectories such that their Fréchet distance is at
most $(1+\varepsilon)d$, and the reference trajectory must be as long as the
maximum of $T_{1}$ and $T_{2}$. Solving this instance of SC is equivalent to
approximating the Fréchet distance of $T_{1}$ and $T_{2}$, and Bringmann [4]
showed that there is no $1.001$-approximation with runtime $O(n^{2-\delta})$
for the continuous Fréchet distance for any $\delta>0$, unless SETH fails.

Since an exact subcubic and an approximate subquadratic algorithm are unlikely
to exist, we study subtrajectory cluster on a realistic family of
trajectories, called $c$-packed trajectories. A trajectory $T$ is $c$-packed
if, for any ball $B$ of radius $r$, the length of $T$ lying inside $B$ is at
most $c$ times $r$. The packedness value of a trajectory $T$ is the maximum
$c$ for which $T$ is $c$-packed. Bringmann [4] proved that computing the
Fréchet distance has no strong subquadratic algorithm unless SETH fails, and
the notion of $c$-packedness was introduced by Driemel et al. [15] to
circumvent such conditional lowerbound. Since then, the notion of
$c$-packedness has gained considerable attention from the theory community
[20, 4, 2, 12, 5], and several real-world data sets have been shown to have
low packedness values [19, 15]. In one particular instance, Gudmundsson et al.
[19] approximated the packedness values of several real-world trajectory data
sets. In their experiments, several trajectory data sets have low packedness
values, such as the movement patterns of people in Beijing, school buses,
European football players, and trawling bats.

In this paper, given a $c$-packed trajectory $T$ of complexity $n$ and a
desired multiplicative approximation error $\varepsilon$ on the Fréchet
distance between subtrajectories, we present an
$O((c^{2}n/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time
algorithm that solves the SC problem. It is worth noting that previous papers
considering $c$-packed curves typically replace a factor $n$ with a polynomial
of constant degree in $c$ [13, 18]. We are able to replace a factor of $n^{2}$
with $c^{2}/\varepsilon^{2}$, bringing the algorithm’s running time from cubic
to near-linear, assuming $c\in O(1)$.

Along the way, we develop a tool for simplifying the free space diagram that
may be of independent interest. To efficiently approximate the Fréchet
distance, Driemel et al. [15] showed that the free space complexity, i.e., the
number of non-empty cells, is $O(cn/\varepsilon)$ for two simplified
$c$-packed trajectories (see Section 2 for an overview of the free space, or
[3] for a formal definition). However, simplifying a trajectory by taking
shortcuts between vertices can yield a much shorter trajectory, and the SC
problem is sensitive to the length of the trajectories since the reference
trajectory has to have a length at least $l$. To tackle this problem, we
developed a tool to construct the free space diagram in
$O((cn/\varepsilon)\log{(cn/\varepsilon)})$ time, preserving the length of two
trajectories while benefiting from the $O(cn/\varepsilon)$ free space
complexity. Our tool can be of value for problems in which the length of a
trajectory is important, such as subtrajectory cluster [8], partial curve
matching [9], and Fréchet distance with speed limit [28].

In Section 2, we will formally define the subtrajectory cluster problem and
outline the greedy plane sweep algorithms by Buchin et al. [8] and Gudmundsson
and Wong [24], which our approach builds on. In Section 3, we provide a
technical overview of our main results. In Section 4, we will discuss how to
simplify the free space diagram to achieve a lower complexity while preserving
trajectory lengths.

In Section 5, we will consider the restricted case when the reference
trajectory must be vertex-to-vertex. In Section 6, we will remove this
restriction by considering arbitrary reference trajectory.

##  2 Preliminaries

In this section, we will outline the previous algorithms for the subtrajectory
cluster problem. The subtrajectory cluster problem was first introduced by
Buchin et al. [8], and later improved by Gudmundsson and Wong [24]. But
instead of looking for a subtrajectory where the Fréchet distances between the
reference trajectory and the subtrajectories are exact, we aim to find a
solution that approximates the Fréchet distance between subtrajectories in the
cluster.

######  Problem 1 ([24]).

Given trajectory $T$ of complexity $n$, a positive integer $m$, positive real
numbers $d$, $l$ and $\varepsilon$, decide if there exists a subtrajectory
cluster of $T$ such that:

  * •

the cluster consists of one reference subtrajectory and $m-1$ other
subtrajectories of $T$,

  * •

the reference subtrajectory has Euclidean length at least $l$,

  * •

the Fréchet distance between the reference subtrajectory and any other
subtrajectory is at most $(1+\varepsilon)d$,

  * •

any pair of subtrajectories in the cluster overlap in at most one point.

Buchin et al. [8] solved the exact SC problem by using a plane sweep algorithm
on the free space diagram $\mathcal{F}_{d}(T,T)$. Let $s$ and $t$ be two
points on $T$, and we denote $T_{st}$ as the subtrajectory of $T$ starting
from $s$ and ending on $t$. Let $l_{s}$ and $l_{t}$ be the vertical sweep
lines $x=s$ and $x=t$ on $\mathcal{F}_{d}(T,T)$, respectively (see Figure 1).
An $xy$-monotone path in $\mathcal{F}_{d}(T,T)$, or monotone path for short,
is a continuous path that is non-decreasing in both $x$\- and $y$-coordinates.
To solve SC(m, d, l), the lines $l_{s}$ and $l_{t}$ sweep from left to right
while making sure that $l_{s}$ is to the left of $l_{t}$, and the reference
trajectory $T_{st}$ is at least $l$ long, i.e., $t-s\geq l$. In each interval
$[l_{s},l_{t}]$, they compute the maximum number of monotone paths in
$\mathcal{F}_{d}(T,T)$ starting at $l_{s}$ and ending at $l_{t}$.

Figure 1: The free space diagram $\mathcal{F}_{d}(T,T)$, and interval
$[l_{s},l_{t}]$ defined by two points $s$ and $t$ on $T$. If there exists a
monotone path (marked in brown) from $(s,p)$ to $(t,q)$ through the free
space, then the Fréchet distance between subtrajectories $T_{st}$ and $T_{pq}$
is at most $d$.

Let $p$ and $q$ be two points on $T$, and let $(s,p)$ and $(t,q)$ be two
coordinates on $\mathcal{F}_{d}(T,T)$. As we only consider monotone paths
starting from $l_{s}$ and ending on $l_{t}$, we call the monotone path from
$(s,p)$ to $(t,q)$ the $pq$ monotone path. First, a monotone path $pq$ must
traverse only the free space. Second, two monotone paths $pq$ and $ab$ must
not overlap along the $y$-interval in more than a single point. Third, the
$y$-coordinates of any $pq$ monotone path cannot overlap the $[s,t]$ interval
in more than a single point. We obtain the following subproblem.

######  Subproblem 2 ([24]).

Given a trajectory $T$ of complexity $n$, a positive integer $m$, a positive
real value $d$, and a reference subtrajectory of $T$ starting at $s$ and
ending at $t$, let $l_{s}$ and $l_{t}$ be two vertical lines in
$\mathcal{F}_{d}(T,T)$ representing the points $s$ and $t$. Decide if there
exist:

  * •

$m-1$ distinct paths starting at $l_{s}$ and ending at $l_{t}$, such that

  * •

the $y$-coordinate of any two monotone paths overlap in at most one point, and

  * •

the $y$-coordinate of any monotone path overlaps the $y$-interval from $s$ to
$t$ in at most one point.

To look for a set $\\{p_{1}q_{1},p_{2}q_{2},...,p_{m-1}q_{m-1}\\}$ of monotone
paths, both algorithms use a greedy approach. First, set $p_{1}$ to be the
lowest feasible point on $l_{s}$, and compute $p_{1}q_{1}$ by searching for a
lowest monotone path through the free space. Inductively, with
$p_{i-1}q_{i-1}$ computed, set $p_{i}$ to the lowest feasible point on $l_{s}$
that is on or above $q_{i-1}$, and do the same. If a search from $p_{i}$ leads
to a dead end, we simply set $p_{i}$ to the next lowest feasible point on
$l_{s}$, and search again.

The sweeplines stop at all $O(n^{3})$ critical points, and for each critical
point there is a $[l_{s},l_{t}]$ interval to consider. Buchin et al. [8]
solved each instance in $O(nm)\subseteq O(n^{2})$ time. Gudmundsson and Wong
[24] improved the efficiency by connecting the critical points efficiently in
a tree-like data structure which allows them to reuse computed monotone paths
from previous interval instances. They showed that, in their construction,
there are at most $O(n^{3}\log n)$ edges, and each edge takes at most $O(\log
n)$ time to add, remove, or access. This brings down the complexity of the
algorithm from $O(n^{5})$ to $O(n^{3}\log^{2}n)$ time.

##  3 Technical Overview

Our technical overview is divided into three parts. In Sections 3.1, 3.2, and
3.3, we summarise the main result of Sections 4, 5, and 6 respectively.

###  3.1 Computing the Free Space Diagram

Our algorithm constructs a simplified free space diagram that preserves
trajectory lengths. The size (in terms of Euclidean length) of the simplified
free space diagram is the same as the size of the unsimplified free space
diagram. The only difference between the two diagrams is that approximate
distances are used in the simplified diagram. In particular, we define a
function that uniformly maps a trajectory to its simplification, and we
calculate the distance between the mapped simplification points instead of
points on the original trajectory. We prove that the complexity of the
simplified free space diagram will be at most $O(cn/\varepsilon)$, and that
the trajectory lengths in the diagram are preserved. Next, we build the
simplified free space diagram. We use an algorithm by Conradi and Driemel [13]
to query pairs of nearby segments. Finally, we construct a data structure on
the free space diagram so that we can access the closest non-empty cells
below, above, to the left, and to the right in constant time. Putting this all
together, we obtain Theorem 3.1. For a full proof, see Section 4.

######  Theorem 3.1.

Given a pair of trajectories, one can construct a simplified free space
diagram in $O((cn/\varepsilon)\log{(cn/\varepsilon)})$ time, so that the
simplified free space has complexity $O(cn/\varepsilon)$, it approximates the
Fréchet distance to within a factor of $(1+\varepsilon)$, and it preserves the
trajectory lengths of the original trajectory.

###  3.2 Reference trajectory is vertex-to-vertex

Next, we focus on the special case where the reference trajectory is vertex-
to-vertex. Three data structures are used in the vertex-to-vertex
subtrajectory cluster algorithm of Gudmundsson and Wong [24] — a directed
graph, a range tree, and a link-cut tree. For an overview of these data
structures, see Appendix A. Originally, the number of leaves per range tree is
$O(n)$, and the directed graph has complexity $O(n^{2})$. We use the
$c$-packedness property to prove that, in our simplified free space diagram,
the number of leaves per range tree is $O(c/\varepsilon)$, and the directed
graph has complexity $O((cn/\varepsilon)\log(c/\varepsilon))$. The link-cut
tree data structure can be used without modification. Putting this all
together, we obtain Theorem 3.2. Recall that $m$ is the desired number of
subtrajectories in the cluster. For a full proof, see Section 5.

######  Theorem 3.2.

There is an $O(nm\log(c/\varepsilon)\log(n/\varepsilon))$ time algorithm that
solves $\mathtt{SC(T,m,l,(1+\varepsilon)d)}$ in the case that the reference
trajectory is vertex-to-vertex.

###  3.3 Reference trajectory is arbitrary

Finally, we tackle the general case where the reference trajectory is
arbitrary. The main obstacle in the general case is that there are
$\Theta(n^{3})$ internal critical points that correspond to potential starting
and ending positions of the reference trajectory. In fact, Gudmundsson and
Wong [24] show that, for general (not $c$-packed) curves, these internal
critical points are essentially unavoidable. They use the $\Theta(n^{3})$
internal critical points to show that under the Strong Exponential Time
Hypothesis (SETH), there is no $O(n^{3-\delta})$ time algorithm for
subtrajectory cluster for any $\delta>0$.

Our main lemma in this section is to bound the number of internal critical
points for subtrajectory cluster on $c$-packed trajectories. The lemma uses
the $c$-packedness property in two different ways. First, the $c$-packedness
property bounds the complexity of the simplified free space diagram to linear.
This replaces one of the factors of $n$ with $c/\varepsilon$. Second, the
$c$-packedness property is used to prove that in any horizontal strip, only a
constant number of cells have free space. This replaces another factor of $n$
with $c/\varepsilon$, resulting in $O(c^{2}n/\varepsilon^{2})$ internal
critical points. Finally, we prove that the interval management data structure
can be used in the same way as in Gudmundsson and Wong’s algorithm [24].
Putting this all together, we obtain Theorem 3.3. For a full proof, see
Section 6.

######  Theorem 3.3.

There is an
$O((c^{2}n/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time
algorithm that solves $\mathtt{SC(T,m,l,(1+\varepsilon)d)}$ in the case that
the reference trajectory is arbitrary.

##  4 Computing the Free Space Diagram

In this section, we will explain the process of constructing a simplified free
space diagram for two $c$-packed polygonal curves $P$ and $Q$. The free space
$\mathcal{D}_{d}(P,Q)$ describes all pairs of points, one on $P$, one on $Q$,
whose distance is at most $d$ [3]. With slight abuse of notation, we
parameterise the polygonal curve $P$ such that $P(x)$ is a point on $P$, where
$x\in[0,\lVert P\rVert]$. Formally,

$\displaystyle\mathcal{D}_{d}(P,Q)=\\{(x,y)\in[0,\lVert
P\rVert]\times[0,\lVert Q\rVert]\mid dist(P(x),Q(y))\leq d\\}.$

To circumvent the quadratic free space complexity, Driemel et al. [15] showed
that the free space complexity of two simplified $c$-packed curves is
$O(cn/\varepsilon)$. Given a $c$-packed curve $P=p_{1}p_{2}...p_{n}$, we
simplify $P$ into its $\varepsilon d$-simplification
$P^{\prime}=q_{1}q_{2}...q_{k}$ as follows. Let $B(a,r)$ be the ball centered
at $a$ with radius $r$. First, set $q_{1}=p_{1}$. With $q_{i}$ defined,
traverse $P$ from $q_{i}$ until a vertex $v$ is outside $B(q_{i},\varepsilon
d)$, or $v$ is the last vertex of $P$, and set $q_{i+1}=v$. Continue until all
vertices of $P$ are exhausted. Driemel et al. [15] showed that the
$\varepsilon d$-simplification of a $c$-packed curve is at most $6c$-packed
[15, Lemma 4.3], and the Fréchet distance between $P$ and $P^{\prime}$ is at
most $(1+\varepsilon)d$. A simplified curve has the useful property that every
segment but the last is at least $\varepsilon d$ long. We assume for
simplicity that the last one is at least $\varepsilon d$ long as well, since
otherwise one can backtrack and modify the simplified curve such that each
segment is at least $\varepsilon d/2$ long, and our arguments can be extended
to such case.

One can simplify a polygonal curve $P$ into its $\varepsilon d$-simplification
$P^{\prime}$ such that the Fréchet distance between $P$ and $P^{\prime}$ is at
most $(1+\varepsilon)d$, and each segment in $P^{\prime}$ is at least
$\varepsilon d$ long.

Simplifying two $c$-packed curves can reduce the free space complexity, but
using the plane-sweep algorithm to solve the SC problem on the resulting free
space diagram is unfortunately infeasible. This is because the total length of
the simplified trajectories can be much shorter, making it impossible to slide
a window of width $l$ on the free space diagram
$\mathcal{F}_{(1+\varepsilon)d}(P^{\prime},Q^{\prime})$. To address this
issue, we developed a tool that enables the construction of a free space
diagram that maintains the original curve length, while also benefiting from
the reduced free space complexity.

###  4.1 Simplifying the Free Space

In this section, we introduce a method that simplifies the free space. We show
that we can construct the simplified free space
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$, where
$\hat{\varepsilon}$ is at most $8\varepsilon$, such that the complexity of the
simplified free space is at most $O(cn/\hat{\varepsilon})$. In addition,
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$ contains
$\mathcal{D}_{d}(P,Q)$ as a subset, but it is not bigger than the free space
of $P$ and $Q$ if we approximate their Fréchet distance, i.e.,
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)\subseteq\mathcal{D}_{(1+\hat{\varepsilon})d}(P,Q)$.

We will first define a function that uniformly maps parts of the polygonal
curve $P$ to segments of $P^{\prime}$ in Definition 4.1, using which we will
formally define the simplified free space in Definition 4.2. We will then
formally prove the set inclusions mentioned above in Lemma 4.3.

######  Definition 4.1.

Let $simpl(P,\varepsilon d)$ be the $\varepsilon d$-simplification of a
polygonal curve $P$. Let $P_{uv}$ be the subcurve of $P$ from point $u$ to $v$
that are simplified into the segment $(u,v)\in simpl(P,\varepsilon d)$. Let
$w$ be the first intersection point of $P_{uv}$ and the boundary of the ball
$B(u,\varepsilon d)$ along $P_{uv}$, and let $u^{\prime}$ be the intersection
of $(u,v)$ and the boundary of the ball $B(u,\varepsilon d)$. Define the
mapping $f_{P,\varepsilon d}:P\rightarrow simpl(P,\varepsilon d)$ such that
$f_{P,\varepsilon d}$ maps $[u,w)$ to $[u,u^{\prime})$ uniformly, and $[w,v]$
to $[u^{\prime},v]$ uniformly (see Figure 2).

Figure 2: A figure showcasing the function in Definition 4.1. The point
$u^{\prime}$ is the intersection of the segment $(u,v)$ and the ball
$B(u,\varepsilon d)$, and the point $w$ is the intersection of subtrajectory
$P_{uv}$ and $B(u,\varepsilon d)$. The function $f_{P,\varepsilon d}$
uniformly maps $P_{uw}$ (red) to $(u,u^{\prime})$ (orange), not including
$u^{\prime}$ and $w$. The function $f_{P,\varepsilon d}$ uniformly maps
$P_{wv}$ (blue) to $(u^{\prime},v)$ (light blue).

######  Definition 4.2.

Define the simplified free space of $P$ and $Q$ with respect to the Fréchet
distance $d>0$, and a parameter $\varepsilon>0$ as

$\displaystyle\mathcal{D}^{\prime}_{(1+\varepsilon)d}(P,Q)=\\{(x,y)\in[0,\lVert
P\rVert]\times[0,\lVert Q\rVert]\mid dist(f_{P,\varepsilon
d}(P(x)),f_{Q,\varepsilon d}(Q(y)))\leq(1+\varepsilon)d\\}.$

Similarly, let $\mathcal{F}^{\prime}_{(1+\varepsilon)d}(P,Q)$ be the
simplified free space diagram.

######  Lemma 4.3.

Let $\mathcal{D}_{d}(P,Q)$ be the free space of curves $P$ and $Q$ with
respect to the Fréchet distance $d$, and let
$\mathcal{D}^{\prime}_{(1+\varepsilon)d}(P,Q)$ be their simplified free space
with an approximation error $\varepsilon>0$. Then
$\mathcal{D}_{d}(P,Q)\subseteq\mathcal{D}^{\prime}_{(1+4\varepsilon)d}(P,Q)\subseteq\mathcal{D}_{(1+8\varepsilon)d}(P,Q)$.

######  Proof 4.4.

With slight abuse of notation, let $x=P(x)$, and $y=Q(y)$, for $x\in[0,\lVert
P\rVert]$, and $y\in[0,\lVert Q\rVert]$. Let $x^{\prime}=f_{P,\varepsilon
d}(x)$, and let $y^{\prime}=f_{Q,\varepsilon d}(y)$. Observe that
$dist(x,x^{\prime})\leq 2\varepsilon d$ for all $x\in P$ because if $x$ is
within the ball $B(u,\varepsilon d)$, then $x$ is at most $2\varepsilon d$
apart from $x^{\prime}$. If $x$ is outside $B(u,\varepsilon d)$, it is at most
$\varepsilon d$ apart from $x^{\prime}$, due to the simplification.

  * •

$\mathcal{D}_{d}(P,Q)\subseteq\mathcal{D}^{\prime}_{(1+4\varepsilon)d}(P,Q)$.
If a point $(x,y)\in\mathcal{D}_{d}(P,Q)$ is white, then $dist(x,y)\leq d$. By
the triangle inequality, $dist(x^{\prime},y^{\prime})\leq
dist(x^{\prime},x)+dist(y^{\prime},y)+dist(x,y)\leq 2\varepsilon
d+2\varepsilon d+d=(1+4\varepsilon)d$, hence $(x^{\prime},y^{\prime})$ must
also be white.

  * •

$\mathcal{D}^{\prime}_{(1+4\varepsilon)d}(P,Q)\subseteq\mathcal{D}_{(1+8\varepsilon)d}(P,Q)$.
Similarly, if a point
$(x^{\prime},y^{\prime})\in\mathcal{D}^{\prime}_{(1+4\varepsilon)d}(P,Q)$ is
white, then $(x,y)\in\mathcal{D}_{(1+8\varepsilon)d}(P,Q)$ must also be white,
because $dist(x,y)\leq
dist(x^{\prime},x)+dist(y^{\prime},y)+dist(x^{\prime},y^{\prime})\leq
2\varepsilon d+2\varepsilon d+(1+4\varepsilon)d=(1+8\varepsilon)d$.

Similar to how we defined the $(u,v)$ cell, let the $(P_{uv},Q_{ab})$ cells be
the cells in the free space diagram defined by the subcurves $P_{uv}$ and
$Q_{ab}$. We show that we can compute the intersection of the simplified free
space with $(P_{uv},Q_{ab})$ cells in constant time.

######  Lemma 4.5.

Given vertices $u,v$ on $P$ and $a,b$ on $Q$, one can construct the cells in
$\mathcal{F}^{\prime}_{(1+\varepsilon)d}(P,Q)$ defined by $P_{uv}$ and
$Q_{ab}$ in constant time.

######  Proof 4.6.

See Appendix B.

The complexity of the simplified free space
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$ is
$O(cn/\hat{\varepsilon})$ if $P$ and $Q$ are $c$-packed. Assuming that
$P_{uv}$ and $Q_{ab}$ are simplified into segments $(u,v)\in P^{\prime}$ and
$(a,b)\in Q^{\prime}$, respectively, the simplified free space intersects
($P_{uv},Q_{ab}$) cells if and only if the distance between $(u,v)$ and
$(a,b)$ is at most $(1+\hat{\varepsilon})d$. The rest follows by modifying the
proof of [15, Lemma 4.4].

######  Corollary 4.7.

Let $P$ and $Q$ be two $c$-packed curves with complexity $n$, and let
$\hat{\varepsilon}$ be a constant times a parameter $\varepsilon>0$. The
complexity of the simplified free space
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$ is $O(cn/\varepsilon)$.

###  4.2 Compute the Non-empty Cells

To take advantage of the near-linear complexity of the simplified free space,
we use an algorithm by Conradi and Driemel [13] to efficiently compute the
non-empty cells without inspecting all pairs of segments.

######  Fact 1 ([13, Lemma 59]).

Given two $c$-packed curves $P$ and $Q$ in $\mathbb{R}^{2}$, a parameter
$d\geq 0$, and let $P^{\prime}$ and $Q^{\prime}$ be their $\varepsilon
d$-simplifications. In $O((cn/\varepsilon)\log(cn/\varepsilon))$ time, one can
find all pairs of segments $(u,v)\in P^{\prime}$ and $(a,b)\in Q^{\prime}$
such that the distance between $(u,v)$ and $(a,b)$ is at most $d$.

To construct the simplified free space diagram efficiently, we first observe
the following.

If segments $(u,v)\in P^{\prime}$ and $(a,b)\in Q^{\prime}$ are more than
$(1+2\varepsilon)d$ apart, then $P_{uv}$ and $Q_{ab}$ are more than $d$ apart.

The above observation enables us to determine if $(P_{uv},Q_{ab})$ cells are
empty by determining if $(u,v)$ and $(a,b)$ are near.

###  4.3 Constructing the Simplified Free Space Diagram

Given two $c$-packed polygonal curves $P$ and $Q$, we will use the results
from previous subsections to construct the simplified free space diagram using
the below steps. In Lemma 4.5, we showed that if $P_{uv}$ and $Q_{ab}$ are
simplified into segments $(u,v)\in P^{\prime}$ and $(a,b)\in Q^{\prime}$,
respectively, we can compute $(P_{uv},Q_{ab})$ cells in constant time. Such
aggregation of $(P_{uv},Q_{ab})$ cells is an aggregated non-empty cell, and we
will treat them as one cell for simplicity.

  1. 1.

Simplify $P$ and $Q$ into their $\varepsilon d$-simplifications $P^{\prime}$
and $Q^{\prime}$.

  2. 2.

Find all pairs of nearby segments from $P^{\prime}$ and $Q^{\prime}$ that are
at most $(1+\hat{\varepsilon})d$ apart using Fact 1.

  3. 3.

For each pair of nearby segments $(u,v)\in P^{\prime}$ and $(a,b)\in
Q^{\prime}$, compute the $(P_{uv},Q_{ab})$ cells using Lemma 4.5.

  4. 4.

Sort all non-empty cells horizontally and vertically.

  5. 5.

Connect non-empty cells in a graph fashion such that a non-empty cell is
connected to the first non-empty cells to its top, bottom, left, and right.

Figure 3: The non-empty cells are connected horizontally and vertically to
skip empty cells.

Given two polygonal curves $P$ and $Q$ of complexity $n$, simplifying them
(step 1) takes $O(n)$ time. By Fact 1, step 2 takes
$O((cn/\varepsilon)\log(cn/\varepsilon))$ time. Computing a cell in
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$ takes $O(1)$ time by
Lemma 4.5. $\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$ has at most
$O(cn/\varepsilon)$ non-empty cells, which takes $O(cn/\varepsilon)$ time to
compute in step 3; sorting them in step 4 takes
$O((cn/\varepsilon)\log(cn/\varepsilon))$ time. Connecting each cell to at
most four other cells takes $O(cn/\varepsilon)$ time in step 5. Putting this
together, we obtain Lemma 4.8, and we summarise our result in Theorem 3.1.

######  Lemma 4.8.

Let $P$ and $Q$ be two $c$-packed curves of complexities $n$. Let
$\varepsilon>0$ and $d>0$ be two parameters, and let $\hat{\varepsilon}\leq
8\cdot\varepsilon$. One can construct and connect $O(cn/\varepsilon)$
aggregated non-empty cells of the simplified free space diagram
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)$ in
$O((cn/\varepsilon)\log{(cn/\varepsilon)})$ time such that
$\mathcal{D}_{d}(P,Q)\subseteq\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(P,Q)\subseteq\mathcal{D}_{(1+\hat{\varepsilon})d}(P,Q)$.
Given an aggregated non-empty cell $C$, one can access the first aggregated
non-empty cells below, above, to the left, and to the right of $C$ in $O(1)$
time.

See 3.1

##  5 Reference trajectory is vertex-to-vertex

Throughout the rest of the paper we assume that the free space diagram is the
simplified free space diagram $\mathcal{F}^{\prime}_{(1+\varepsilon)d}$ in
Lemma 4.8. Next, we will use the algorithm by Gudmundsson and Wong [24] to
determine whether there is a solution to $\mathtt{SC(T,m,l,(1+\varepsilon)d)}$
where $T$ is a $c$-packed trajectory, and the reference subtrajectory is
vertex-to-vertex.

Three data structures are used in the vertex-to-vertex subtrajectory cluster
algorithm of Gudmundsson and Wong [24] — a directed graph, a range tree, and a
link-cut tree. For an overview of these data structures, see Appendix A. In
Section 5.1, we show that the number of leaves per range tree is
$O(c/\varepsilon)$, and the directed graph has complexity
$O((cn/\varepsilon)\log(c/\varepsilon))$. In Section 5.2, we show that the
link-cut tree data structure can be used without modification.

###  5.1 Using a Directed Graph to Store Candidate Monotone Paths

To show that the range tree has at most $O(c/\varepsilon)$ leaves, it suffices
to show that there exist at most $O(c/\varepsilon)$ critical points on each
horizontal or vertical boundary of the simplified free space diagram.

######  Lemma 5.1.

In the simplified free space diagram
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$, let $H$ be a horizontal
(resp. vertical) strip that is at least $\varepsilon d$ wide on its $y$-span
(resp. $x$-span). The intersection of $H$ and the simplified free space
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$ exists in at most
$O(c/\varepsilon)$ aggregated cells.

######  Proof 5.2.

Let $T^{\prime}$ be the $\varepsilon d$-simplification of $T$, and let
$T_{uv}$ simplifies into segment $(u,v)\in T^{\prime}$. Let
$u^{\prime}\subseteq(u,v)$ be a small part that is at least $\varepsilon d$
long. Let $S_{u^{\prime}}=u^{\prime}\oplus B(0,(1+\hat{\varepsilon})d)$.

Using similar construction, and arguments of [15, Lemma 4.4], one can prove
that at most $O(c/\varepsilon)$ segments in $T^{\prime}$ intersects
$S_{u^{\prime}}$. Based on the construction of the simplified free space
$\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$, a point
$(x,y)\in\mathcal{D}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$ is white if and
only if
$dist(f_{T,\hat{\varepsilon}d}(T(x)),f_{T,\hat{\varepsilon}d}(T(y)))\leq(1+\hat{\varepsilon})d$.
As such, at most $O(c/\varepsilon)$ aggregated cells have simplified free
space intersecting $H$.

Next, bound the construction time and space complexity of the directed graph
in [24].

######  Lemma 5.3.

Given a $c$-packed trajectory $T$ of complexity $n$, constructing $G$ for the
simplified free space diagram
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$ takes
$O((cn/\varepsilon)\log{(n/\varepsilon)})$ time. $G$ has $O(cn/\varepsilon)$
nodes and $O((cn/\varepsilon)\log{(c/\varepsilon)})$ edges.

######  Proof 5.4.

Let $n_{k}$ be the number of non-empty aggregated cells in the $j$th row in
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$. Construction of the
range tree for the top (resp. right) boundary of a row (resp. column) takes
$O(n_{k}\log{n_{k}})$ time [14]. For all $p_{i}$, finding $q_{i}$ takes
$O(n_{k}\log{n_{k}})$ time and recall that there are $O(cn/\varepsilon)$
critical points in $\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$. The
total construction time is as follows.

$\displaystyle\sum_{j=0}^{n+1}n_{k}\log{n_{k}}\leq\log{\left(\frac{cn}{\varepsilon}\right)}\sum_{j=0}^{n+1}n_{k}=\log{\left(\frac{cn}{\varepsilon}\right)}O\left(\frac{cn}{\varepsilon}\right)\in
O\left(\left(\frac{cn}{\varepsilon}\right)\log{\left(\frac{n}{\varepsilon}\right)}\right)$

By Corollary 4.7, the simplified free space diagram has $O(cn/\varepsilon)$
non-empty aggregated cells, therefore $G$ has $O(cn/\varepsilon)$ nodes. In a
range tree, given a continuous interval $[q_{k},q_{i}]$, one can find
$O(\log{n})$ nodes such that these nodes include $[q_{k},q_{i}]$ in their
canonical subset, where $n$ is the total number of items in the leaves [14].
There are at most $O(c/\varepsilon)$ nodes on a horizontal or vertical
boundary by Lemma 5.1, and each critical point $p_{i}$ on a vertical (resp.
horizontal) cell boundary connects to $O(\log(c/\varepsilon))$ nodes,
therefore the total number of edges is
$O((cn/\varepsilon)\log(c/\varepsilon))$.

###  5.2 Storing and Reusing Pre-computed Paths

A link-cut tree [29] maintains a forest that allows the link/cut operations of
subtrees in $O(\log{n})$ amortised time. In addition, a link-cut tree allows
finding the root of a node in $O(\log{n})$ amortised time. The algorithm by
Gudmundsson and Wong [24] used a link-cut tree to store and re-use monotone
paths. Consider when a sweepline, either $l_{s}$ or $l_{t}$, stops at a new
critical point $p$. Instead of recomputing the monotone paths, they need only
to add $p$ to the existing link-cut tree they maintained in the previous
instances.

With graph $G$ defined, we can analyse the total running time of the algorithm
by Gudmundsson and Wong [24] on the simplified free space diagram. The key to
observe the running time is that in their algorithm, if an edge leads to a
dead-end, it is marked and will not be used in future searches. Furthermore,
inserting or removing an edge takes $O(\log n)$ amortised time in a link-cut
tree.

See 3.2

######  Proof 5.5.

Construction of the simplified free space diagram takes
$O((cn/\varepsilon)\log{(cn/\varepsilon)})$ time by Theorem 3.1. Construction
of $G$ takes $O((cn/\varepsilon)\log{(n/\varepsilon)})$ time by Lemma 5.3. The
graph $G$ has at most $O(nm\log(c/\varepsilon))$ edges, see Appendix C.
Gudmundsson and Wong [24] showed that an edge is added to and removed from the
link-cut tree at most once, and adding/removing an edge from the link-cut tree
takes $O(\log(n/\varepsilon))$ time since the maximum number of nodes in the
link-cut tree is upperbounded by the number of nodes in $G$. Therefore
maintaining the link-cut tree takes
$O(nm\log(c/\varepsilon)\log(n/\varepsilon))$ time.

##  6 Reference trajectory is arbitrary

Our results in this section rely heavily on the work of Gudmundsson and Wong
[24]. Due to space constraints, we can only highlight important parts of their
algorithm, and the analysis of our improvements.

When the reference trajectory is arbitrary, a monotone path can start and
finish at arbitrary positions in the non-empty cells. Therefore, in addition
to the critical points in the free space diagram and the greedy critical
points, Gudmundsson and Wong defined three new types of internal critical
points [24, Definition 25]. An internal critical point must lie in the
interior of a non-empty cell, and lie on the boundary of the free space. They
made the following distinction (see Figure 4).

  1. 1.

End-of-cell critical point: the leftmost and rightmost white point of a non-
empty cell.

  2. 2.

Propagated critical point: a point on the boundary of the free space that
shares a $y$-coordinate with a critical point.

  3. 3.

$l$-apart critical points: two points on the boundaries of free space that are
a distance of $l$ apart horizontally.

Figure 4: The three types of internal critical points are illustrated using a
cross in the left, middle, and right figures, respectively. From left to
right, they are the end-of-cell critical points (left), propagated critical
points (middle) and $l$-apart critical points (right).

There could be an infinite number of $l$-apart critical points in a pair of
non-empty cells. However, if this is the case, we can simply perturb the input
by a miniscule amount so that there are no longer an infinite number of
$l$-apart critical points. See Appendix E for an example and a figure.
Therefore, for the rest of the paper, we can assume that there are at most a
constant number of $l$-apart critical points per pair of cells.

We will first bound the number of internal critical points and the time it
takes to compute them. One can compute the end-of-cell and $l$-apart critical
points in linear time with respect to the number of non-empty cells since
there are at most a constant number of them per pair of cells. In Lemma 5.1,
we showed that in a narrow horizontal strip, only a small number of cells
intersect free space. An output-sensitive query algorithm would be efficient
to find the non-empty cells that a critical point $p$ propagates to.
Therefore, we can use an interval tree [14] to store the $y$-spans of all non-
empty cells in a row, and query the intersecting intervals of $y(p)$ in
logarithmic time. We formalise the above arguments in the below Lemma 6.1.

######  Lemma 6.1.

Assume that there is a constant number of $l$-apart critical points per pair
of cells, it takes $O(cn\log(n/\varepsilon)+c^{2}n/\varepsilon^{2})$ time to
compute $O(c^{2}n/\varepsilon^{2})$ internal critical points in the simplified
free space diagram $\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$.

######  Proof 6.2.

There are $O(cn/\varepsilon)$ non-empty aggregated cells in
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$, or non-empty cells for
short, and $O(cn/\varepsilon)$ end-of-cell critical points in
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$. Each critical point
propagates $O(c/\varepsilon)$ times by Lemma 5.1, therefore there are
$O(c^{2}n/\varepsilon^{2})$ propagated critical points. We can charge a cell
with a constant number of $l$-apart critical points. Therefore, there are at
most $O(cn/\varepsilon)$ $l$-apart critical points. In total, there are
$O(c^{2}n/\varepsilon^{2})$ internal critical points.

One can compute the end-of-cell critical points by iterating through the free
space diagram in $O(cn/\varepsilon)$ time. To compute the $l$-apart critical
points, we can start from the first non-empty cell $C$ in a row and find the
first cell that is $l$-apart from $C$, and solve a constant number of
quadratic equations. We can then slide this $l$-apart line and do the same for
all pairs of cells that are $l$-apart in all rows in $O(cn/\varepsilon)$ time
in total.

To compute the propagated critical points, we construct an interval tree [14]
for each row in $\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$ to store
the maximum and minimum $y$-coordinates of the free space in the non-empty
cells. Let $n_{i}$ be the number of non-empty cells in the $i$th row. We can
sum the construction time of the interval trees.

$\displaystyle\sum_{i=1}^{n}n_{i}\log
n_{i}\leq\frac{cn}{\varepsilon}\log\left(\frac{cn}{\varepsilon}\right)\in
O\left(\left(\frac{cn}{\varepsilon}\right)\log\left(\frac{cn}{\varepsilon}\right)\right)$

Given a critical point $p$ in the $i$th row, one can query the interval tree
in $O(\log{n_{i}}+c/\varepsilon)\in O(\log n+c/\varepsilon)$ time to compute
the propagated critical points from $p$ using Lemma 5.1 and [14]. With
$O(cn/\varepsilon)$ critical points, computing the propagated critical points
takes $O(cn\log(n)/\varepsilon+c^{2}n/\varepsilon^{2})$ time.

With the additional internal critical points, the number of reference
trajectories and the number of greedy critical points increases. We can use
the algorithm in the previous section, and obtain the following result.

######  Lemma 6.3.

There is an
$O((c^{2}mn/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time
algorithm that solves $\mathtt{SC(T,m,l,(1+\varepsilon)d)}$ in the case that
the reference trajectory is arbitrary.

######  Proof 6.4.

See Appendix D.

###  6.1 Improve Further with an Interval Management Data Structure

The bottleneck in the above Lemma 6.3 is operating the outgoing edges of the
$O(c^{2}mn/\varepsilon^{2})$ greedy critical points, which are generated from
$O(c^{2}n/\varepsilon^{2})$ propagated critical points. To avoid computing the
greedy critical points, Gudmundsson and Wong [24] used a dynamic monotonic
interval data structure [16] to store overlapping monotonic intervals that
represent the $y$-spans of monotone paths between $l_{s}$ and $l_{t}$. Instead
of searching for a set of monotone paths between each window greedily, they
showed that one can update and query the interval data structure to retrieve
$m-1$ non-overlapping intervals, all in $O(\log n)$ amortised time.

See 3.3

######  Proof 6.5.

Constructing the simplified free space diagram takes
$O((cn/\varepsilon)\log{(cn/\varepsilon)})$ time by Theorem 3.1. Computing and
sorting the internal critical points takes
$O((c^{2}n/\varepsilon^{2})\log(n/\varepsilon))$ time by Lemma 6.1. There are
$O((c^{2}n/\varepsilon^{2})\log(c/\varepsilon))$ edges in total by Lemma 5.1,
and each edge takes $O(\log(n/\varepsilon))$ time to insert or remove since
there are at most $O(c^{2}n/\varepsilon^{2})$ nodes in the link-cut tree. In
total, we spend
$O((c^{2}n/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time to
maintain the edges in $G$.

Each internal critical point is treated as an event, and maintaining the
interval data structure takes $O(\log n)$ amortised time per event point (see
[24, Theorem 2]), and thus $O((c^{2}n/\varepsilon^{2})\log n)$ in total. The
overall complexity is dominated by maintaining the edges.

##  7 Conclusion

We presented an algorithm that solves the subtrajectory cluster problem on
$c$-packed trajectories $T$ with an approximation error on the Fréchet
distance, achieving an
$O((c^{2}n/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time
complexity. Our algorithm builds upon the near-optimal algorithm proposed by
Gudmundsson and Wong [24], but with significant improvements. By carefully
analysing the properties of $c$-packed trajectories, we have shown that
important parameters such as the number of propagated critical points are
significantly lower than the theoretical $O(n)$ upperbound for realistic
trajectories. As a result, our algorithm improves upon the near-optimal
algorithm by replacing a factor of $n^{2}$ with $c^{2}/\varepsilon^{2}$,
leading to more efficient subtrajectory cluster of realistic trajectories.

## References

  * [1] Pankaj K. Agarwal, Kyle Fox, Kamesh Munagala, Abhinandan Nath, Jiangwei Pan, and Erin Taylor.  Subtrajectory Clustering: Models and Algorithms.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’18, pages 75–87, New York, NY, USA, May 2018. Association for Computing Machinery.
  * [2] Sepideh Aghamolaei, Vahideh Keikha, Mohammad Ghodsi, and Ali Mohades.  Windowing queries using Minkowski sum and their extension to MapReduce.  The Journal of Supercomputing, 77(1):936–972, January 2021.
  * [3] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  International Journal of Computational Geometry & Applications, 05:75–91, March 1995.
  * [4] Karl Bringmann.  Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661–670, October 2014.  ISSN: 0272-5428.
  * [5] Karl Bringmann and Marvin Künnemann.  Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds.  International Journal of Computational Geometry & Applications, 27:85–119, March 2017.
  * [6] Frederik Brüning, Jacobus Conradi, and Anne Driemel.  Faster Approximate Covering of Subcurves Under the Fréchet Distance.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISSN: 1868-8969.
  * [7] Kevin Buchin, Maike Buchin, David Duran, Brittany Terese Fasy, Roel Jacobs, Vera Sacristan, Rodrigo I. Silveira, Frank Staals, and Carola Wenk.  Clustering trajectories for map construction.  In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’17, pages 1–10, New York, NY, USA, November 2017. Association for Computing Machinery.
  * [8] Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo.  Detecting commuting patterns by clustering subtrajectories.  International Journal of Computational Geometry & Applications, 21(03):253–282, June 2011.
  * [9] Kevin Buchin, Maike Buchin, and Yusu Wang.  Exact algorithms for partial curve matching via the Fréchet distance.  In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, SODA ’09, pages 645–654, USA, January 2009. Society for Industrial and Applied Mathematics.
  * [10] Claudia Cavallaro, Armir Bujari, Luca Foschini, Giuseppe Di Modica, and Paolo Bellavista.  Measuring the impact of COVID-19 restrictions on mobility: A real case study from Italy.  Journal of Communications and Networks, 23(5):340–349, October 2021\.
  * [11] Cheng Chang and Baoyao Zhou.  Multi-granularity visualization of trajectory clusters using sub-trajectory clustering.  In 2009 IEEE International Conference on Data Mining Workshops, pages 577–582, December 2009.
  * [12] Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, and Carola Wenk.  Approximate map matching with respect to the Fréchet distance.  In 2011 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), Proceedings, pages 75–83. Society for Industrial and Applied Mathematics, January 2011.
  * [13] Jacobus Conradi and Anne Driemel.  On Computing the k-Shortcut Fréchet Distance.  In Miko\laj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISSN: 1868-8969.
  * [14] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.  Computational Geometry: Algorithms and Applications.  Springer, Berlin, Heidelberg, 2008.
  * [15] Anne Driemel, Sariel Har-Peled, and Carola Wenk.  Approximating the Fréchet distance for realistic curves in near linear time.  Discrete & Computational Geometry, 48(1):94–127, July 2012.
  * [16] Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, and Jiamou Liu.  Dynamic algorithms for monotonic interval scheduling problem.  Theoretical Computer Science, 562:227–242, January 2015.
  * [17] Joachim Gudmundsson, Martin P. Seybold, and John Pfeifer.  On practical nearest sub-trajectory queries under the Fréchet distance.  In Proceedings of the 29th International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’21, pages 596–605, New York, NY, USA, November 2021. Association for Computing Machinery.
  * [18] Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong.  Map matching queries on realistic input graphs under the Fréchet distance.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1464–1492. Society for Industrial and Applied Mathematics, January 2023.
  * [19] Joachim Gudmundsson, Yuan Sha, and Sampson Wong.  Approximating the packedness of polygonal curves.  Computational Geometry, 108:101920, January 2023.
  * [20] Joachim Gudmundsson and Michiel Smid.  Fréchet queries in geometric trees.  In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms – ESA 2013, pages 565–576, Berlin, Heidelberg, 2013. Springer.
  * [21] Joachim Gudmundsson, Andreas Thom, and Jan Vahrenhold.  Of motifs and goals: mining trajectory data.  In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’12, pages 129–138, New York, NY, USA, November 2012. Association for Computing Machinery.
  * [22] Joachim Gudmundsson and Nacho Valladares.  A GPU approach to subtrajectory clustering using the Fréchet distance.  IEEE Transactions on Parallel and Distributed Systems, 26(4):924–937, April 2015.
  * [23] Joachim Gudmundsson and Thomas Wolle.  Football analysis using spatio-temporal tools.  In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’12, pages 566–569, New York, NY, USA, November 2012. Association for Computing Machinery.
  * [24] Joachim Gudmundsson and Sampson Wong.  Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 173–189. Society for Industrial and Applied Mathematics, January 2022.
  * [25] Sariel Har-Peled.  Geometric Approximation Algorithms.  American Mathematical Society, USA, 2011.
  * [26] Amin Hosseinpoor Milaghardan, Rahim Ali Abbaspour, Christophe Claramunt, and Alireza Chehreghan.  An activity-based framework for detecting human movement patterns in an urban environment.  Transactions in GIS, 25(4):1825–1848, 2021.
  * [27] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang.  Trajectory clustering: a partition-and-group framework.  In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, SIGMOD ’07, pages 593–604, New York, NY, USA, June 2007. Association for Computing Machinery.
  * [28] Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, and Hamid Zarrabi-Zadeh.  Fréchet distance with speed limits.  Computational Geometry, 44(2):110–120, February 2011.
  * [29] Daniel D. Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  Journal of Computer and System Sciences, 26(3):362–391, June 1983\.
  * [30] Panagiotis Tampakis, Nikos Pelekis, Christos Doulkeridis, and Yannis Theodoridis.  Scalable distributed subtrajectory clustering.  In Proceedings of the 2019 IEEE International Conference on Big Data (Big Data), pages 950–959. IEEE Computer Society, December 2019.
  * [31] Zheng Wang, Cheng Long, and Gao Cong.  Similar sports play retrieval with deep reinforcement learning.  IEEE Transactions on Knowledge and Data Engineering, pages 1–1, 2021.

##  Appendix A The Directed Graph of Gudmundsson and Wong [24]

In this section, we will discuss the construction of a directed graph to store
candidate monotone paths, as proposed by Gudmundsson and Wong [24]. They
defined a specific type of monotone path that exists in a row or column only,
and showed that any general monotone path $P$ can be decomposed into a series
of these so-called basic monotone paths $P^{\prime}$, such that the $y$-span
of $P$ is a subset of the $y$-span of $P^{\prime}$. The basic monotone paths
are stored in a directed graph, which can be efficiently queried to find
feasible monotone paths.

######  Definition A.1 ([24]).

A basic monotone path is a monotone path that is contained entirely in a
single row or column of the free space diagram, starting at a critical point
on a vertical cell boundary, and ending on a critical point on a horizontal
cell boundary, or vice versa.

Gudmundsson and Wong [24, Lemma 16] showed that there is a monotone path from
critical point $a$ to $b$ on the free space diagram if and only if there is a
sequence of basic monotone paths between $a$ and $b$. Their idea is to
decompose a monotone path into path $p_{1}p_{2}...p_{k}$ such that $p_{1}=a$,
$p_{k}=b$, and the path from $p_{i}$ to $p_{i+1}$ is a basic monotone path.
One can first transform a monotone path $Q$ into a set of almost-basic
monotone paths $q_{1}...q_{k}$ inductively: if $q_{i}$ lies on a vertical
(resp. horizontal) cell boundary, then $q_{i+1}$ is the next intersection of
$Q$ with a horizontal (resp. vertical) boundary. Then one can transform the
path $q_{1}...q_{k}$ into a series of basic monotone path as follows. If
$q_{i}$ lies on a vertical (resp. horizontal) cell boundary, then $p_{i}$ is
the critical point below (resp. left of) $q_{i}$.

######  Fact 2 ([24, Lemma 16]).

Given a pair of critical points $a$ and $b$ in the free space diagram, there
is an $ab$ monotone path if and only if there is a sequence of basic monotone
paths $p_{1}...p_{k}$ such that $p_{i}$ is a critical point for $1\leq i\leq
k$, $p_{1}=a$, and $p_{k}=b$.

With basic monotone paths defined, we want to construct a graph to store all
possible basic monotone paths. We will do so row-by-row and column-by-column.
For an arbitrary row, where $H$ is the top boundary, let $p_{i}$ be the
bottom-most critical point of the $i$th vertical cell boundary, where $0\leq
i\leq n+1$. A brute-force approach is to connect every $p_{i}$ to every
critical point $q$ on $H$ such that there is a $p_{i}q$ basic monotone path.
However, the number of edges is cubic in this case.

Define $q_{i}$ to be the rightmost critical point on the top boundary such
that there is a $p_{i}q_{i}$ basic monotone path. A key observation is that if
there is a $p_{i}q_{i}$ monotone path, then there is a $pq$ monotone path
where $q$ is a critical point on $H$, $q$ is to the right of $p_{i}$ and to
the left of $q_{i}$. Indeed, let $r$ be the intersection of the $p_{i}q_{i}$
monotone path with the left vertical cell boundary of the cell that contains
$r$. Since the interior of a non-empty cell is convex, there is a $pr$
monotone path.

The above observation enables Gudmundsson and Wong to define a graph $G=(V,E)$
to efficiently store all possible basic monotone paths [24]. For an arbitrary
row, they first construct a range tree $RT$ storing the critical points on $H$
with respect to their increasing $x$-coordinates. Then, they connect $p_{i}$
to the node $v$ in $RT$ as long as there is a basic monotone path from $p_{i}$
to every critical point in the leaves of $v$ (see Figure 5). Each column of
the free space diagram is processed analogously. As we will use the range tree
extensively in the following section, we define the canonical subset to
differentiate from the canonical squares defined in the previous section.
Given a node $v$ in a range tree, the canonical subset of $v$ is the set of
points stored in the leaves of $v$ [14].

Figure 5: Part of graph $G$. We build a directed range tree from the critical
points on the top boundary. A bottom critical point $p$ on a vertical cell
boundary is connected to a node $v$ of the range tree as long as there is a
basic monotone path from $p$ to every critical point in the canonical subset
of $v$, which are illustrated with dashed lines.

Gudmundsson and Wong [24] described an algorithm that find $q_{i}$ for each
$p_{i}$, However, we cannot use their algorithm for two reasons. First, their
algorithm only works on the very restrictive case when all non-empty cells
have critical points on their top boundary, which is not true in the free
space diagram of two general curves. Second, their algorithm only works when
all cells in a row are non-empty.

We will now show how to find $q_{i}$ for each $p_{i}$. Let $r_{i}$ be the top
critical point on a vertical cell boundary. For some $p_{i}$ on a $i$th
vertical cell boundary, we can draw a horizontal line to the right from
$p_{i}$. If this horizontal line is blocked first immediately before the the
$j$th vertical cell boundary and $y(p_{i})\leq y(p_{j})$ (resp. $y(p_{i})\geq
y(r_{j})$), we say $p_{i}$ is blocked by $p_{j}$ (resp. $r_{j}$).

There are two things that can happen (see Figure 6). One, the line is blocked
by some point $b$ on the boundary between free and non-free space in the cell
immediately to the left of $r_{j}$ or $p_{j}$. $b$ is either higher than
$r_{j}$ or lower than $p_{j}$. If $b$ is below some $p_{j}$, then
$q_{i}=q_{j}$ since there is a $p_{i}p_{j}q_{j}$ monotone path. If $b$ is
above some $r_{j}$, then $q_{i}$ is simply the rightmost critical point on $H$
that is to the left of $r_{j}$ and to the right of $p_{i}$. Second, the line
from $p_{i}$ is blocked at point $b$ by the non-free space that completely
separates two adjacent cells or it is blocked by the right boundary of the
free space diagram. Say $b$ lies between the $j$th and the $(j-1)$th vertical
cell, then $q_{i}$ is simply the rightmost critical point on $H$ that is to
the left of the $j$th vertical cell boundary and to the right of $p_{i}$.

Figure 6: In the left figure, $p_{1}$ is blocked by $p_{2}$. In the right
figure, $p_{1}$ is blocked by $r_{3}$.

Knowing the above, given $p_{i}$, if we can find the first $p_{j}$ or $r_{j}$
that blocks $p_{i}$, we can find $q_{i}$. We can use a binary search tree to
store the top and bottom critical points of the vertical cell boundaries based
on their increasing $x$-coordinates, where critical points on the same
vertical cell boundary are stored in the same leaf. In addition, each node $v$
stores the maximum and minimum $y$-coordinates of the critical points in $v$’s
canonical subset. One can query such binary search tree to find the first
$p_{j}$ or $r_{j}$ that blocks $p_{i}$ in $O(\log n)$ time. In fact, we can do
the same thing for any arbitrary point $p$ in the free space as long as we
know which cell $p$ reside in.

Given a set of $n_{k}$ consecutive non-empty cells in the same row with
vertical boundary indices $\\{1,...,n_{k}+1\\}$, one can preprocess them in
$O(n_{k}\log n_{k})$ time such that one can find the first $p_{j}$ or $r_{j}$
that blocks $p$ in $O(\log n)$ time.

With the above observation, and the dynamic programming algorithm described by
Gudmundsson and Wong [24, Lemma 20], we can preprocess the free space diagram
such that given a free point $p$, we can find the rightmost critical point on
the top boundary of the same row in $O(\log n)$ time. This property is useful
in Section 6 when the reference trajectory is no longer vertex-to-vertex, and
a monotone path can start from the interior of a non-empty cell. We combine
the above insights and observation in the below Lemma A.2.

######  Lemma A.2.

Given a row of $n_{k}$ non-empty cells in the free space diagram and a point
$p$ in the free space, one can preprocess these cells in $O(n_{k}\log n_{k})$
time, and find the right-most critical point $q$ on the top boundary such that
there is a $pq$ monotone path in $O(\log n_{k})$ time.

######  Proof A.3.

Given a row of non-empty cells, we use the below algorithm on each set of
consecutive adjacent non-empty cells such that the boundary between two cells
intersects free space. Let $x(p)$ and $y(p)$ be the $x$ and $y$-coordinate of
point $p$, respectively. Let the index of the leftmost and rightmost vertical
boundary be $l$ and $r$, respectively.

Preprocess the row using Observation A in $O(n_{k}\log n_{k})$ time. Iterate
$i$ from $r$ to $l$, and for each $p_{i}$, use Observation A to find the
leftmost $p_{j}$ or $r_{j}$ such that $y(p_{i})\leq y(p_{j})$ or $y(p_{i})\geq
y(r_{j})$, respectively, in $O(\log n_{k})$ time. If $p_{j}$ is leftmost, set
$q_{i}=q_{j}$. If $r_{j}$ is leftmost, use binary search to find the rightmost
critical point $q$ such that $x(p_{i})\leq x(q)\leq x(r_{j})$ in $O(\log
n_{k})$ time. In total, this takes $O(n_{k}\log n_{k})$ time. Then, given a
free point $p$ between the $i$th and the $(i+1)$th cell boundaries, one can
find the first $p_{j}$ or $r_{j}$ that blocks $p_{i}$, and repeat the above
process to find the rightmost critical point $q$ such that there is a $pq$
monotone path in $O(\log n_{k})$ time.

The correctness of this algorithm relies on two key facts. One, if $p_{j}$ is
the leftmost critical point such that $p_{i}$ is blocked by $p_{j}$, then
there is a $p_{i}p_{j}$ monotone path. Second, if $r_{j}$ is the leftmost
critical point that blocks $p_{i}$, then there is a $pq$ monotone path as long
as $q$ is between $p_{i}$ and $r_{j}$. Indeed, since the intersection of the
free space and a cell is convex, if $p_{i}$ is not blocked by any critical
point of a cell $C$, $p_{i}$ cannot be blocked by the interior of $C$.

##  Appendix B Proof of Lemma 4.5

See 4.5

######  Proof B.1.

The following definition follows from the definition of $f_{P,\varepsilon d}$.
Let $u^{\prime}$ be the first intersection of $B(u,\varepsilon d)$ and $(u,v)$
along $simpl(P,\varepsilon d)$, and let $a^{\prime}$ be the first intersection
of $B(a,\varepsilon d)$ and $(a,b)$ along $simpl(Q,\varepsilon d)$. Let $w$ be
the first intersection of $B(u,\varepsilon d)$ and $P_{uv}$, and let $c$ be
the first intersection of $B(a,\varepsilon d)$ and $Q_{ab}$.

Consider a partition of $(P_{uv},Q_{ab})$ cells into four cells generated from
$P_{uw}$, $P_{wv}$, $Q_{ac}$, and $Q_{cb}$. Define $W$ to be the rectangle
$[0,\lVert P_{uw}\rVert]\times[0,\lVert Q_{ac}\rVert]$. We will show that the
intersection of the simplified free space and $(P_{uw},Q_{ac})$ cells is an
ellipse clipped at $W$ by using the arguments in the proof of [25, Lemma
30.2.1].

With slight abuse of notation, we redefine $P_{uw}$ as the affine mapping from
$[0,\lVert P_{uw}\rVert]$ to points on $P_{uw}$. The function
$f_{P,\varepsilon d}\circ P_{uw}$ is an affine function as the composition of
two affine functions $f_{P,\varepsilon d}$ and $P_{uw}$ is also affine, and
similarly, $f_{Q,\varepsilon d}\circ Q_{ab}$ is affine. Therefore
$h:(x,y)\mapsto f_{P,\varepsilon d}(P_{uw}(x))-f_{Q,\varepsilon d}(Q_{ab}(y))$
is an affine function. And assuming general position of $(u,v)$ and $(a,b)$,
$h$ is also one-to-one. All the desired configurations of $(x,y)$ values
satisfying $\lVert h(x,y)\rVert\leq d$ are mapped to the disk $B$ with radius
$d$ centered at the origin.

Consider the intersection of $B$ and the image of $h$, i.e.,
$h(\mathbb{R}^{2})\cap B$, then the simplified free space of the
$(P_{uw},Q_{ac})$ cells is the set $h^{-1}(h(\mathbb{R}^{2})\cap B)\cap W$.
The inverse of an affine function is also an affine function, and as such so
is $h^{-1}$. The affine image of a disk is an ellipse, and as such so is
$h^{-1}(h(\mathbb{R}^{2})\cap B)$. Therefore the $(P_{uw},Q_{ac})$ cell is an
ellipse clipped into a rectangle, and it takes constant time to compute.

The above arguments can be extended to the other three cells. Therefore,
constructing the cells defined by $P_{uw}$ and $Q_{ab}$ in
$\mathcal{F}^{\prime}_{(1+\varepsilon)d}(P,Q)$ takes constant time.

##  Appendix C Handling Additional Critical Points

There are additional critical points to consider. With monotone path $P_{i}$
computed, the start of $P_{i+1}$ should be the lowest feasible free point $p$
on $l_{s}$. Similarly, the finishing point of a monotone path should be the
lowest feasible free point $p^{\prime}$ on $l_{t}$. We will call these points
$p$ and $p^{\prime}$ the greedy critical points, and they may not be in $G$.
Gudmundsson and Wong [24] showed that the number of greedy critical points is
bounded by $O(nm)$, that is, $m$ monotone paths for each of the $O(n)$
reference trajectories.

We also need to add the greedy critical points in $G$. Recall that in Lemma
A.2, we describe an algorithm to compute, for a point $p$ in the free space,
the rightmost critical point $q$ on the top boundary such that there is a $pq$
monotone path in $O(\log n_{k})$ time if $p$ belongs to a group of $n_{k}$
consecutive non-empty cells. We have also shown that there are only
$O(c/\varepsilon)$ critical points on a horizontal boundary. We can now bound
the number of greedy critical points, the time it takes to insert them into
$G$, and the total number of edges of $G$ with the additional greedy critical
points.

######  Lemma C.1.

In the simplified free space diagram
$\mathcal{F}^{\prime}_{(1+\hat{\varepsilon})d}(T,T)$, we generate at most
$O(nm)$ greedy critical points. It takes $O(nm\log n)$ time to add them in the
graph $G$, and $G$ has at most $O(nm\log(c/\varepsilon))$ edges.

######  Proof C.2.

There are at most $O(nm)$ greedy critical points [24]. For each greedy
critical point $p$, it takes $O(\log n)$ amortised time to find the rightmost
critical point $q$ such that there is a $pq$ basic monotone path, and it takes
$O(\log(c/\varepsilon))$ time to range query the $O(\log(c/\varepsilon))$
nodes to connect $p$ to in the range tree. In total, it takes $O(nm\log n)$
time to insert the greedy critical points in $G$. Each $p$ connects to at most
$O(\log{(c/\varepsilon)})$ nodes, therefore we add at most
$O(nm\log(c/\varepsilon))$ edges. The graph $G$ has $O(nm\log(c/\varepsilon))$
edges in total.

##  Appendix D Proof of Lemma 6.3

See 6.3

######  Proof D.1.

Construction of the simplified free space diagram takes
$O(cn/\varepsilon+cn/\varepsilon^{3})$ by Theorem 3.1. Construction of $G$
takes $O((cn/\varepsilon)\log{(n/\varepsilon)})$ time by Lemma 5.3. The total
number of critical points is upperbounded by the number of propagated critical
points, which is $O(c^{2}n/\varepsilon^{2})$. The total number of greedy
critical point is $O((c^{2}n/\varepsilon^{2})\cdot m)$. Sorting the critical
points takes $O((c^{2}mn/\varepsilon^{2})\log(n/\varepsilon))$ time. For every
critical point $p$, compute the rightmost point $q$ such that there is a $pq$
monotone path takes $O((c^{2}nm/\varepsilon^{2})\log n)$ time by Lemma A.2.
The graph $G$ has at most $O((c^{2}mn/\varepsilon^{2})\log(c/\varepsilon))$
edges after adding the greedy critical points, and the internal critical
points. Gudmundsson and Wong [24] showed that an edge is added to and removed
from the link-cut tree at most once, and adding/removing an edge from the
link-cut tree takes $O(\log(n/\varepsilon))$ time since the maximum number of
nodes in the link-cut tree is upperbounded by the number of nodes in $G$.
Therefore maintaining the link-cut tree takes
$O((c^{2}mn/\varepsilon^{2})\log(c/\varepsilon)\log(n/\varepsilon))$ time.

##  Appendix E Infinite $l$-apart Critical Points

One can detect that two cells generate infinite $l$-apart critical points by
comparing the quadratic equations of their interiors (see Figure 7). To cope
with this case, one can move the end point of one of the segment by a
miniscule amount, say $\delta=\varepsilon^{2}d$.

Figure 7: The placement of segments $u$, $v$, and $v^{\prime}$ and their
respective $(u,v)$ and $(u,v^{\prime})$ cells. There are an infinite number of
$l$-apart critical points when the boundaries of the free space in two cells
can be expressed with the same equation, and they are exactly $l$-apart.