Department of Information and Computing Sciences, Utrecht University, the
Netherlands and Department of Mathematics and Computer Science, TU Eindhoven,
the Netherlands<EMAIL_ADDRESS>Department of Information and
Computing Sciences, Utrecht University, the Netherlands and Department of
Mathematics and Computer Science, TU Eindhoven, the Netherlands
<EMAIL_ADDRESS>Thijs van der Horst, and Tim Ophelders [100]Theory of
computation Computational Geometry

# Faster Fréchet Distance Approximation through Truncated Smoothing

Thijs van der Horst  Tim Ophelders

###### Abstract

The Fréchet distance is a popular distance measure for curves. Computing the
Fréchet distance between two polygonal curves of $n$ vertices takes roughly
quadratic time, and conditional lower bounds suggest that even approximating
to within a factor $3$ cannot be done in strongly-subquadratic time, even in
one dimension. The current best approximation algorithms present trade-offs
between approximation quality and running time. Recently, van der Horst et al.
(SODA, 2023) presented an $O((n^{2}/\alpha)\log^{3}n)$ time
$\alpha$-approximate algorithm for curves in arbitrary dimensions, for any
$\alpha\in[1,n]$. Our main contribution is an approximation algorithm for
curves in one dimension, with a significantly faster running time of
$O(n\log^{3}n+(n^{2}/\alpha^{3})\log^{2}n\log\log n)$. Additionally, we give
an algorithm for curves in arbitrary dimensions that improves upon the state-
of-the-art running time by a logarithmic factor, to
$O((n^{2}/\alpha)\log^{2}n)$. Both of our algorithms rely on a linear-time
simplification procedure that in one dimension reduces the complexity of the
reachable free space to $O(n^{2}/\alpha)$ without making sacrifices in the
asymptotic approximation factor.

###### keywords:

Frécht distance, approximation algorithms, simplification

###### category:

##  1 Introduction

Comparing curves is an important task in for example trajectory analysis [14],
handwriting recognition [24] and matching time series in data bases [23]. To
compare curves, one needs a suitable distance measure. The Hausdorff distance
is a commonly used distance measure when comparing sets of points. However,
although each curve corresponds

to a set of points, a point set by itself does not capture the order in which
points appear along the curve. This may lead to curves having low Hausdorff
distance, even when they are clearly very different. See for example the
curves on the right. The Fréchet distance is a distance measure that does take
the ordering of points along the curves into account, and hence compares
curves more accurately.

The first algorithm for computing the Fréchet distance between polygonal
curves was given by Godau [21], who presented an $O(n^{3}\log n)$ time
algorithm for two curves with $n$ vertices in total. Alt and Godau [2] later
improved the result to an $O(n^{2}\log n)$ time algorithm. The discrete
version of the problem was first studied by Eiter and Mannila [19], who gave
an $O(n^{2})$ time algorithm.

These results have since been improved in the word RAM model of computation.
For example, Agarwal et al. [1] gave an $O(n^{2}\log\log n/\log n)$ time
algorithm for the discrete problem, and Buchin et al. [9] later improved the
complexity bound for the continuous problem to $O(n^{2}(\log\log n)^{2})$.
Unfortunately there is strong evidence that these results cannot be improved
significantly, since Bringmann [5] showed that a _strongly-subquadratic_
(i.e., $n^{2-\Omega(1)}$) time algorithm would refute the _Strong Exponential
Time Hypothesis_ (SETH).

Due to the conditional lower bound, we will focus on efficient _approximation
algorithms_. When the curves are from certain families of “realistic” curves,
strongly-subquadratic time $(1+\varepsilon)$-approximation algorithms are
known to exist. For example, if the curves are either _$\kappa$ -bounded_ or
_backbone_ curves, the algorithm by Aronov et al. [3] gives a
$(1+\varepsilon)$-approximation to the discrete Fréchet distance in
$O(n^{4/3}\log n/\varepsilon^{2})$ time. Later on, Driemel et al. [17]
presented $(1+\varepsilon)$-approximate algorithms for the continuous Fréchet
distance that take near-linear time, given that the curves are from one of
four realistic curve classes. These four classes includes $\kappa$-bounded
curves, but also _$c$ -packed_, _$\varphi$ -low density_ and _$\kappa$
-straight_ curves. Their result on $c$-packed curves was improved by Bringmann
and Künnemann [7], whose algorithm matches conditional lower bounds.

When approximating the Fréchet distance between arbitrary curves, SETH again
gives conditional lower bounds. The lower bound by Bringmann [5] holds not
only for exact algorithms, but for $1.001$-approximate algorithms as well.
This lower bound was later improved by Buchin et al. [10], who showed that
under SETH, no strongly-subquadratic $(3-\varepsilon)$-approximation algorithm
exists, even for curves in one dimension. For the current strongly-
subquadratic algorithms, the best known approximation factor is polynomial
($n^{\varepsilon}$) for both the discrete and the continuous Fréchet distance.
Whether a strongly-subquadratic constant factor approximation algorithm exists
remains open.

For the discrete Fréchet distance, Bringmann and Mulzer [8] gave a linear time
greedy algorithm with an approximation factor of $2^{\Theta(n)}$. They also
presented the first strongly-subquadratic time algorithm with polynomial
approximation factor. For any $\alpha\in[1,n/\log n]$, their algorithm gives
an $\alpha$-approximation in $O(n^{2}/\alpha)$ time. This result was later
improved by Chan and Rahmati [13], who gave an $O(n^{2}/\alpha^{2})$ time
algorithm, for any $\alpha\in[1,\sqrt{n/\log n}]$.

For continuous Fréchet distance, the first polynomial approximation algorithm
running in strongly-subquadratic time is due to Colombe and Fox [15]. They
gave an $\alpha$-approximate algorithm running in $O(n\log
n+(n^{3}/\alpha^{2})\log n)$ time. Recently, van der Horst et al. [25]
presented the first algorithm that supports arbitrarily small polynomial
approximation factors in strongly-subquadratic time
$O(n\log^{3}n+(n^{2}/\alpha)\log^{3}n)$.

##### Results.

The basis of our results is a curve simplification algorithm. We use the
resulting simplified versions of two curves to efficiently approximate the
Fréchet distance between the input curves. Doing so, we improve the running
time of the algorithm by van der Horst et al. [25] significantly for curves in
one dimension, and by a logarithmic factor in higher dimensions. Our running
time in one dimension is $O(n\log^{3}n+(n^{2}/\alpha^{3})\log^{2}n\log\log
n)$, in contrast to our $O(n\log n+(n^{2}/\alpha)\log^{2}n)$ time algorithm
for higher dimensions. We summarize our algorithms in Section 2, but first we
define the Fréchet distance and some useful notation.

## Preliminaries

A $d$-dimensional (polygonal) _curve_ is a piecewise-linear function
$P\colon[0,1]\to\mathbb{R}^{d}$, connecting a sequence $p_{1},\dots,p_{n}$ of
$d$-dimensional points, which we refer to as _vertices_. The linear
interpolation between $p_{i}$ and $p_{i+1}$, whose image is equal to the
directed line segment $\overline{p_{i}p_{i+1}}$, is called an _edge_. We
denote by $P[x_{1},x_{2}]$ the subcurve of $P$ over the domain
$[x_{1},x_{2}]$. We write $|P|$ to denote the number of vertices of $P$.

##### Fréchet distance.

A _reparameterization_ of $[0,1]$ is a non-decreasing, continuous surjection
$f\colon[0,1]\to[0,1]$. Two reparameterizations $f,g$ describe a _matching_
$(f,g)$ between two curves $P$ and $Q$, where any point $P(f(t))$ is matched
to $Q(g(t))$. A matching $(f,g)$ between $P$ and $Q$ is said to have _cost_

$\max_{t}\|P(f(t))-Q(g(t))\|.$

It is common to use the Euclidean norm $\|P(f(t))-Q(g(t))\|_{2}$ to measure
the cost of a matching. For our purposes however, it is more convenient to use
the $L_{\infty}$ norm $\|P(f(t))-Q(g(t))\|_{\infty}$. Since we aim for at
least polynomial approximation factors, and the norms differ by at most a
factor $\sqrt{d}$, approximations using the $L_{\infty}$ norm implies the same
asymptotic approximation factor for the Euclidean norm, as long as $d$ is
constant. A matching with cost at most $\delta$ is called a _$\delta$
-matching_. The (continuous) _Fréchet distance_ $d_{F}(P,Q)$ between $P$ and
$Q$ is the minimum cost over all matchings.

##### Free space diagram and matchings.

The _free space diagram_ of $P$ and $Q$ is the parameter space $[0,1]^{2}$ of
$P\times Q$, denoted $\mathcal{D}(P,Q)$. Any point $(x,y)\in\mathcal{D}(P,Q)$
corresponds to the pair of points $P(x)$ and $Q(y)$ on the two curves. Any
pair of edges $(P[x_{1},x_{2}],Q[y_{1},y_{2}])$ corresponds to a _cell_
$[x_{1},x_{2}]\times[y_{1},y_{2}]$ of $\mathcal{D}(P,Q)$.

For $\delta\geq 0$, a point $(x,y)\in\mathcal{D}(P,Q)$ is _$\delta$ -close_ if
$\|P(x)-Q(y)\|_{\infty}\leq\delta$. The _$\delta$ -free space_
$\mathcal{F}_{\leq\delta}(P,Q)$ of $P$ and $Q$ is the subset of
$\mathcal{D}(P,Q)$ containing all $\delta$-close points. A point
$z_{2}=(x_{2},y_{2})\in\mathcal{F}_{\leq\delta}(P,Q)$ is _$\delta$ -reachable_
from a point $z_{1}=(x_{1},y_{1})$ if there exists a bimonotone path in
$\mathcal{F}_{\leq\delta}(P,Q)$ from $z_{1}$ to $z_{2}$. Points that are
$\delta$-reachable from $(0,0)$ are simply called $\delta$-reachable points.
Alt and Godau [2] observe that the Fréchet distance between $P[x_{1},x_{2}]$
and $Q[y_{1},y_{2}]$ is at most $\delta$ if and only if there is a bimonotone
path in $\mathcal{F}_{\leq\delta}(P,Q)$ from $z_{1}$ to $z_{2}$. We therefore
abuse terminology slightly and refer to a bimonotone path from $z_{1}$ to
$z_{2}$ as a $\delta$-matching between $P[x_{1},x_{2}]$ and $Q[y_{1},y_{2}]$.

##  2 Algorithmic outline

Figure 1: An illustration of the approximate decision algorithm.

Let $P$ and $Q$ be our two $d$-dimensional input curves with a total of $n$
vertices. Given a parameter $\alpha\geq 1$, we describe an _$\alpha$
-approximate decision algorithm_ for the continuous Fréchet distance. Such an
algorithm takes as input an additional parameter $\delta\geq 0$, and must
correctly report that $d_{F}(P,Q)\leq\alpha\delta$ or that
$d_{F}(P,Q)>\delta$. If $d_{F}(P,Q)\in(\delta,\alpha\delta]$, the algorithm
may report either. We thus either confirm that an $\alpha\delta$-matching
exists, or assert that no $\delta$-matching exists. Refer to Figure 1 for a
diagram illustrating our algorithm. We turn our decision algorithms into
approximation algorithms for the Fréchet distance with the procedure of
Colombe and Fox [15] (with logarithmic overhead in the running time and
arbitrarily small increase in approximation ratio).

Recall that a $\delta$-matching between $P$ and $Q$ represents a bimonotone
path from $(0,0)$ to $(1,1)$ in the $\delta$-free space
$\mathcal{F}_{\leq\delta}(P,Q)$. Our algorithms search for such a path.
However, exploring all of the free space, which may have $\Theta(n^{2})$
complexity, does not result in a subquadratic time algorithm. Still, the
worst-case complexity of the _reachable_ free space, the part of free space
containing all $\delta$-reachable points, is smaller for certain types of
curves. We explore this in Section 3, where we investigate the relation
between the complexity of the reachable free space and the number of _narrow
pieces_ on the curves. If the number of such pieces is $k$, then the reachable
free space complexity is only $O(kn)$ _blocks_. Here, a block is a
generalization of cells, that instead of edges considers monotone pieces.
Specifically, a block is the rectangular region of the free space diagram
corresponding to two monotone pieces, one of $P$ and one of $Q$.

Given that a sublinear number of narrow pieces implies a subquadratic
complexity of the reachable free space, we present a simplification procedure
in Section 4 that reduces the total number of narrow pieces to at most
$dn/\alpha$, at an additive factor of $2\alpha$ to the approximation ratio,
see Figure 1 (a–b). The simplification takes linear time, and results in a
reachable free space complexity of only $O(n^{2}/\alpha)$ blocks, see Figure 1
(c). Intuitively, the proportion of the free space diagram that we need to
explore is inversely proportional to the approximation factor.

The complexity of the free space inside a block $B_{i,j}$ corresponding to
monotone pieces $P_{i},Q_{j}$ is $O(|P_{i}|\cdot|Q_{j}|)$. This is too large
even when considering only the $O(n^{2}/\alpha)$ blocks containing the
reachable free space, as these blocks may still have a combined complexity of
$\Theta(n^{2})$. However, the free space inside a block is ortho-convex, see
Figure 1 (d). We use this fact in Section 7 to construct a data structure on
$P$ and $Q$ for traversing $B_{i,j}$ in just $O((|P_{i}|+|Q_{j}|)\log n)$
time, after $O(n)$ time preprocessing. This gives an $O(n+(n^{2}/\alpha)\log
n)$ time algorithm for traversing all $O(n^{2}/\alpha)$ blocks, and hence
gives an $O(n+(n^{2}/\alpha)\log n)$ time $(2\alpha+1)$-approximate decision
algorithm.

The technique by Colombe and Fox [15] can be applied to turn the decision
algorithm into an $\alpha$-approximation algorithm for the Fréchet distance,
with a running time of $O(n\log n+(n^{2}/\alpha)\log^{2}n)$.

Figure 2: An illustration of the approximate decision algorithm for one-
dimensional curves.

In Sections 5 and 6 we give a faster algorithm for when $P$ and $Q$ are one-
dimensional curves. Figure 2 illustrates this algorithm. The core of the
algorithm is a subroutine for constructing _approximate exit sets_ (see the
bottom diagram of Figure 2). Given a set of points
$S\subseteq\\{0\\}\times[0,1]$ on the left side of the free space diagram, an
$(\alpha,\delta)$-exit set for $S$ is a set of points
$E_{\alpha}(S)\subseteq\\{1\\}\times[0,1]$ on the right side of the diagram
that contains all points that are $\delta$-reachable from $S$, and only points
that are $\alpha\delta$-reachable from $S$. If $(1,1)\in
E_{\alpha}(\\{(0,0)\\})$, then $d_{F}(P,Q)\leq\alpha\delta$, and otherwise
$d_{F}(P,Q)>\delta$. Computing such exit sets thus generalizes the approximate
decision problem.

We construct approximate exit sets in Section 6. For this we use the ideas of
Chan and Rahmati [13] for the current state-of-the-art discrete approximate
decision algorithm. They construct a graph approximately representing the free
space, which can be used to construct approximate exit sets (in the discrete
setting). These exit sets take only $O(n\log n+n^{2}/\alpha^{2})$ time to
construct.

To achieve a similar running time in the continuous setting, we first note
that continuous matchings in one dimension are relatively discrete. In
particular, _signature vertices_ , special vertices introduced by Driemel et
al. [18], must match in an almost discrete manner, matching to points close to
vertices of the other curve. With this in mind, we apply the techniques of
Chan and Rahmati [13] to the signature vertices of $P$.

We construct an infinite grid $\mathbb{G}$ with few _bad_ vertices of both $P$
and $Q$. See Figure 2 (f–g). This grid has cellwidth $\alpha\delta$, and we
classify a point as bad if it is within distance $7\delta$ of the boundary of
$\mathbb{G}$. Chan and Rahmati [13] show that by shifting $P$ and $Q$, the
number of bad vertices can be made as low as $O(n/\alpha)$. We say that a
signature vertex of $P$ is bad if it is within distance $6\delta$ of the
boundary of $\mathbb{G}$, rather than within distance $7\delta$. These
vertices must match to points close to bad vertices of $Q$, and hence have
essentially only $O(n/\alpha)$ possible ways to match to points.

Between two bad signature vertices of $P$, the signature vertices are all
sufficiently far from the boundary of $\mathbb{G}$ that we can represent them
by the gridcells containing them, after which matchings become effectively
diagonal. We can detect such matchings with the exact string matching data
structure by Chan and Rahmati [13], and use an additional data structure to
handle the matchings around bad signature vertices. For a single entrance, we
can then efficiently compute an $(\alpha,\delta)$-exit sets for any subcurve
between two subsequent bad signature vertices, see Figure 2 (h–i). The data
structure constructs such a set in only $O(\log n\log\log n)$ time. Applied to
all $O(n^{2}/\alpha^{2})$ possible matchings with a bad signature vertex of
$P$, we get an $O((n^{2}/\alpha^{2})\log n\log\log n)$ time algorithm for
constructing $(\alpha,\delta)$-exit sets of general sets of points, after
$O(n\log^{2}n)$ time preprocessing.

The above algorithm is already an improvement over the higher-dimensional
case, but we can improve the algorithm by taking advantage of the lower-
complexity reachable free space. Given that the reachable free space stays
within $O(n/\alpha)$ cells of the diagonal, we cover this region by $\alpha$
rectangles of size $O(n/\alpha)\times O(n/\alpha)$ cells. See Figure 2 (c–d).
In each rectangle we construct an $(\alpha,\delta)$-exit set for a given set
of entrance points, which depend on the exit set of the rectangle to the left
of the current one. These exit sets take only
$O((n/\alpha)\log^{2}n+(n^{2}/\alpha^{4})\log n\log\log n)$ time to construct
for a rectangle, totalling $O(n\log^{2}n+(n^{2}/\alpha^{3})\log n\log\log n)$
time. This is a factor $\alpha$ improvement, which we would expect given the
lower complexity of the reachable free space.

The technique by Colombe and Fox [15] turns our algorithm for constructing a
$(\alpha,\delta)$-exit set into an
$O(n\log^{3}n+(n^{2}/\alpha^{3})\log^{2}n\log\log n)$ time
$\alpha$-approximate algorithm for the Fréchet distance.

##  3 Bounding the reachable free space

The complexity of the $\delta$-free space can be as high as $\Theta(n^{2})$,
meaning that explicitly traversing the free space does not give a strongly-
subquadratic time algorithm. As an improvement, we aim to bound the complexity
of the _reachable $\delta$-free space_, the subset of $\delta$-free space that
is reachable by a bimonotone path from $(0,0)$. This subset contains all
bimonotone paths to $(1,1)$, so it suffices to consider only this subset.

Like the complexity of free space, the complexity of the reachable free space
can be quadratic. Still, there are special cases of curves for which we can
check if the top-right point $(1,1)$ is reachable in as little as linear time.
One example is when the edges of one of the curves are _long_ , meaning their
lengths are all strictly greater than $4\delta$ (see the work of Gudmundsson
et al. [22]). Under the $L_{\infty}$ norm, which is the chosen norm in this
work, van der Horst et al. [25] generalize the result to the case where one
curve is the concatenation of long _monotone_ curves.

A curve is monotone if in every coordinate it is either non-increasing or non-
decreasing. A curve $P$ is the concatenation of maximal monotone pieces
$P_{1},\dots,P_{k}$. We call the curves $P_{1},\dots,P_{k}$ the _monotone
decomposition_ of $P$, and call the individual monotone curves $P_{i}$
_(monotone) pieces_ of $P$. A monotone curve is long if the $L_{\infty}$
distance between its endpoints is strictly greater than $4\delta$, and is
short otherwise. In the next section, we investigate a class of monotone
curves that we call _$\eta$ -narrow_ curves. A monotone curve is $\eta$-narrow
if its bounding box has at least one side of length at most $\eta$. As an
example, short monotone curves are $4\delta$-narrow, although $4\delta$-narrow
curves are not necessarily short. See Figure 3 for concrete examples. We show
that there is a relation between the number of $2\delta$-narrow monotone
pieces of $P$ and $Q$ and the complexity of the reachable free space.

Figure 3: From left to right: two $2\delta$-narrow curves, a short curve
(which is $4\delta$-narrow) and a curve that is not $4\delta$-narrow (which is
long).

Under the $L_{\infty}$ norm, the monotone pieces of a curve behave much like
line segments. Most importantly, any ball under the $L_{\infty}$ norm
intersects a piece in at most one connected component. For the free space,
this implies that the subset of $\mathcal{D}(P,Q)$ that corresponds to a
monotone piece of $P$ and a monotone piece of $Q$ has an ortho-convex111 A
region $S$ is ortho-convex if every line parallel to a coordinate axis
intersects $S$ in at most one connected component.  intersection with the
$\delta$-free space, for all $\delta\geq 0$. This somewhat generalizes the
convexity of the free space within a cell (defined by two line segments) to
unions of cells that together are defined by two monotone pieces.

We define a _block_
$B_{i,j}\coloneqq[x_{i},x_{i+1}]\times[y_{j},y_{j+1}]\subseteq\mathcal{D}(P,Q)$
to be the subset of $\mathcal{D}(P,Q)$ corresponding to a monotone piece
$P_{i}=P[x_{i},x_{i+1}]$ and a monotone piece $Q_{j}=Q[y_{j},y_{j+1}]$. This
block is the union of the cells defined by the edges of $P_{i}$ and $Q_{j}$.
We associate $\mathcal{D}(P,Q)$ with its partitioning into blocks. The _block
diagonal_ consists of the blocks $B_{i,i}$ and we say that block $B_{i,j}$ is
$|i-j|$ blocks away from the (block) diagonal.

For our algorithm, we analyse the complexity of the reachable free space in
terms of blocks, rather than cells. In particular, we bound the number of
blocks that reachable points can be away from the diagonal in terms of the
number of narrow pieces. In the following theorem we show that the number of
blocks a reachable point can be away from the block diagonal depends linearly
on the number of $2\delta$-narrow pieces of $P$ and $Q$.

######  Theorem 3.1.

Let $P$ and $Q$ be two $d$-dimensional curves, each with at most $k$ monotone
pieces that are $2\delta$-narrow. Then any $\delta$-reachable point lies
within $2k+1$ blocks of the block diagonal.

######  Proof 3.2.

Assume for ease of exposition that $P$ and $Q$ contain no degenerate vertices.
Suppose for sake of contradiction that a $\delta$-reachable point $z$ lies
more than $2k+1$ blocks right of the diagonal. Let $\pi$ be a bimonotone path
to this point. Because $z$ lies more than $2k+1$ blocks right of the diagonal,
there must be more than $2k$ pairs of blocks $B_{i,j},B_{i+1,j}$ that $\pi$
traverses from the left side of $B_{i,j}$ to the right side of $B_{i+1,j}$. We
argue that the number of such pairs is at most $2k$, which gives a
contradiction.

Consider a pair of blocks $B_{i,j},B_{i+1,j}$ of blocks that $\pi$ traverses
from the bottom side of $B_{i,j}$ to the top side of $B_{i+1,j}$. We show that
either $P_{i}$ or $P_{i+1}$ is $2\delta$-narrow. To this end, suppose that
both $P_{i}$ and $P_{i+1}$ are not $2\delta$-narrow. Because $\pi$ traverses
$B_{i,j}$ from left to right, there is a subcurve
$Q^{\prime}_{j}=Q_{j}[y,y^{\prime}]$ of $Q_{j}$ with
$\|P_{i}(0)-Q^{\prime}_{j}(0)\|_{\infty}\leq\delta$ and
$\|P_{i}(1)-Q^{\prime}_{j}(1)\|_{\infty}\leq\delta$. This means that
$Q^{\prime}_{j}$ is more than a single point, and that it has the same
direction with respect to the coordinate axes as $P_{i}$. However, $P_{i+1}$
has the opposite direction with respect to at least one coordinate axis, and
since it is not $2\delta$-narrow, its last endpoint $P_{i+1}(1)$ is more than
distance $\delta$ away from $Q^{\prime}_{j}(1)$. Therefore it is more than
distance $\delta$ away from all of $Q_{j}[y^{\prime},1]$. Hence $\pi$ cannot
traverse $B_{i+1,j}$ from left to right if both $P_{i}$ and $P_{i+1}$ are not
$2\delta$-narrow.

With the above, we charge each pair of blocks $B_{i,j},B_{i+1,j}$ that $\pi$
traverses from the left side of $B_{i,j}$ to the right side of $B_{i+1,j}$ to
one of the $2\delta$-narrow pieces of $P$ corresponding to these blocks. As
each narrow piece corresponds to at most two such pairs, pieces are charged at
most twice. It follows that there are at most $2k$ such pairs of blocks, which
gives a contradiction. This shows that $z$ is at most $2k+1$ blocks right of
the diagonal. That $z$ is at most $2k+1$ blocks above the diagonal follows
from a symmetric argument.

##  4 Reducing the number of narrow pieces

We present a family of simplifications for curves that we use to reduce the
number of narrow pieces on a curve. The simplifications are based on truncated
smoothings for Reeb graphs [12], and we hence call them truncated smoothings.

###  4.1 Truncated smoothings

First consider a one-dimensional curve $P$. We assume for ease of exposition
that $P$ has no degenerate vertices.222 Note that if $P$ has degenerate
vertices, then the curve obtained by deleting these vertices has Fréchet
distance $0$ to $P$.  Let $\varepsilon\geq 0$ be at most half the minimum edge
length of $P$. The _truncated $\varepsilon$-smoothing_ $P^{\varepsilon}$ of
$P$ is the curve obtained by truncating every edge of $P$ by $\varepsilon$ on
either side. See Figure 4 for an example. We extend the truncated smoothing
definition to all non-negative values $\varepsilon^{\prime}\geq 0$ by
recursively defining the truncated $\varepsilon^{\prime}$-smoothing of $P$ for
$\varepsilon^{\prime}>\varepsilon$ to be the truncated
$(\varepsilon^{\prime}-\varepsilon)$-smoothing of $P^{\varepsilon}$.

Figure 4: An illustration of truncated smoothings in one dimension. (left) The
vertices of curve $P$ (non-dashed) are drawn as vertical segments for clarity.
The minimum edge length of $P$ is realized by $\overline{p_{i}p_{i+1}}$
(right) The result of the smoothing procedure (non-shaded).

The Fréchet distance between $P$ and its truncated $\varepsilon$-smoothing
$P^{\varepsilon}$ is at most $\varepsilon$ for all $\varepsilon$.
Specifically, the identity matching, which matches a point $P(x)$ to the point
$P^{\varepsilon}(x)$, has cost at most $\varepsilon$. We use this fact
together with the triangle inequality to show that truncated
$\varepsilon$-smoothings can be used for an additive
$2\varepsilon$-approximation for the Fréchet distance.

######  Lemma 4.1.

Let $P$ be a one-dimensional curve. For any $\varepsilon\geq 0$, the identity
matching between $P$ and $P^{\varepsilon}$ has cost at most $\varepsilon$.

######  Proof 4.2.

Let $\varepsilon\geq 0$ and let $\varepsilon^{\prime}$ be half the minimum
edge length of $P$. Consider a point $P(x)$ on $P$. We show that
$|P(x)-P^{\varepsilon}(x)|\leq\varepsilon$. If
$\varepsilon\leq\varepsilon^{\prime}$ then the point $P^{\varepsilon}(x)$ is
trivially within distance $\varepsilon$ of $P(x)$. For general $\varepsilon$,
applying the triangle inequality to the recursive definition of the
simplification yields that

$|P(x)-P^{\varepsilon}(x)|\leq\begin{cases}\varepsilon&\text{if
$\varepsilon\leq\varepsilon^{\prime}$,}\\\
|P(x)-P^{\varepsilon-\varepsilon^{\prime}}(x)|+\varepsilon^{\prime}&\text{otherwise}.\end{cases}$

This implies $|P(x)-P^{\varepsilon}(x)|\leq\varepsilon$. The identity matching
is therefore an $\varepsilon$-matching between $P$ and $P^{\varepsilon}$.

######  Lemma 4.3.

Let $P$ and $Q$ be two one-dimensional curves. For all $\varepsilon\geq 0$ we
have $d_{F}(P^{\varepsilon},Q^{\varepsilon})\leq d_{F}(P,Q)\leq
d_{F}(P^{\varepsilon},Q^{\varepsilon})+2\varepsilon$.

######  Proof 4.4.

Let $\varepsilon\geq 0$ and set $\delta=d_{F}(P,Q)$. Applying the triangle
inequality to a given $\delta$-matching $\varphi$ between $P^{\varepsilon}$
and $Q^{\varepsilon}$ and the identity matchings between $P$ and
$P^{\varepsilon}$ and between $Q$ and $Q^{\varepsilon}$, we obtain from Lemma
4.1 that $\varphi$ is a $(\delta+2\varepsilon)$-matching between $P$ and $Q$.
Next let $\psi$ be a $\delta$-matching between $P$ and $Q$. It again follows
from the triangle inequality that $\psi$ is a $(\delta+2\varepsilon)$-matching
between $P^{\varepsilon}$ and $Q^{\varepsilon}$, but we show through a more
involved analysis that $\psi$ has cost at most $\delta$.

We assume without loss of generality that $P$ and $Q$ contain no degenerate
vertices, and further assume without loss of generality that $\varepsilon$ is
at most half the minimum edge length of $P$ and $Q$. Let $P(x)$ be matched to
$Q(y)$ by $\psi$. Suppose for sake of contradiction that
$|P^{\varepsilon}(x)-Q^{\varepsilon}(y)|>\delta$. We consider four different
cases based on the positions of $P^{\varepsilon}(x)$ and $Q^{\varepsilon}(y)$
relative to $P(x)$ and $Q(y)$.

  1. 1.

For the first case, suppose that $P^{\varepsilon}(x)\leq P(x)$ and
$Q^{\varepsilon}(y)\geq Q(y)$. If
$P^{\varepsilon}(x)>Q^{\varepsilon}(y)+\delta$ then we have $P(x)\geq
P^{\varepsilon}(x)>Q^{\varepsilon}(y)+\delta\geq Q(y)+\delta$, which gives a
contradiction. However, if $P^{\varepsilon}(x)<Q^{\varepsilon}(y)-\delta$,
then $P(x)\leq
P^{\varepsilon}(x)+\varepsilon<Q^{\varepsilon}(y)+\varepsilon-\delta\leq
Q(y)-\delta$, implying that $|P(x)-Q(y)|>\delta$ and giving a contradiction as
well. Hence we must have that
$|P^{\varepsilon}(x)-Q^{\varepsilon}(y)|\leq\delta$ in this case.

  2. 2.

The second case, where $P^{\varepsilon}(x)\geq P(x)$ and
$Q^{\varepsilon}(y)\leq Q(y)$, is symmetric to the first.

  3. 3.

For the third case, suppose that $P^{\varepsilon}(x)<P(x)$ and
$Q^{\varepsilon}(y)<Q(y)$. Let $P^{\prime}=P[x_{1},x_{2}]$ be the smallest
subcurve of $P$ with $x_{1}\leq x\leq x_{2}$ and
$P(x_{1})=P(x_{2})=P^{\varepsilon}(x)$. Analogously, let
$Q^{\prime}=Q[y_{1},y_{2}]$ be the smallest subcurve of $Q$ with $y_{1}\leq
y\leq y_{2}$ and $Q(y_{1})=Q(y_{2})=Q^{\varepsilon}(y)$. Note that
$P^{\prime}$ lies in the interval
$[P^{\varepsilon}(x),P^{\varepsilon}(x)+\varepsilon]$ and that $Q^{\prime}$
lies in the interval $[Q^{\varepsilon}(y),Q^{\varepsilon}(y)+\varepsilon]$,
and that both curves have points on them that attain the extrema of these
intervals. Because $\psi$ matches $P(x)$ to $Q(y)$, it must match either
$P(x_{1})$ to a point on $Q^{\prime}$, or $Q(y_{1})$ to a point on
$P^{\prime}$. Also, it must match either $P(x_{2})$ to a point on
$Q^{\prime}$, or $Q(y_{1})$ to a point on $P^{\prime}$.

Assume that $P^{\varepsilon}(x)<Q^{\varepsilon}(y)-\delta$, the other case is
symmetric. Both $P(x_{1})$ and $P(x_{2})$ have distance greater than $\delta$
to $Q^{\varepsilon}(y)$, and therefore to all points on $Q^{\prime}$. Hence we
must have that $Q(y_{1})$ and $Q(y_{2})$ are both matched to points on
$P^{\prime}$, and by the definition of matchings, all points on $Q^{\prime}$
are matched to points on $P^{\prime}$. However, $Q^{\prime}$ contains a point
with value $Q^{\varepsilon}(y)+\varepsilon$, whose distance to any point on
$P^{\prime}$ is greater than $\delta$. This contradicts the assumption that
$\psi$ is a $\delta$-matching, proving that
$|P^{\varepsilon}(x)-Q^{\varepsilon}(y)|\leq\delta$ in this case.

  4. 4.

The fourth case, where $P^{\varepsilon}(x)>P(x)$ and
$Q^{\varepsilon}(y)>Q(y)$, is symmetric to the third.

Next we give a crucial property of truncated smoothings for one-dimensional
curves, showing that we can bound the number of edges of any given length to
any given amount with some truncated smoothing. The value of the required
parameter of course depends on the desired bounds.

######  Lemma 4.5.

Let $P$ and $Q$ be two one-dimensional curves with $n$ vertices. For all
$\alpha\in[1,n]$ and $\delta\geq 0$, there is an $\varepsilon\leq c\alpha$ for
which $P^{\varepsilon}$ and $Q^{\varepsilon}$ together have at most $n/\alpha$
edges of length at most $2\delta$.

######  Proof 4.6.

We assume for ease of exposition that $P$ and $Q$ contain no degenerate
vertices. Let $\alpha\in[1,n]$ and $\delta\geq 0$. We first argue that
$P^{\delta}$ and $Q^{\delta}$ together have fewer than $n-n/\alpha$ vertices.

We charge the vertices of $P$ and $Q$ that are degenerate in $P^{\delta}$ and
$Q^{\delta}$ to the edges of $P$ and $Q$ that have length at most $2\delta$.
Let $e$ be such an edge. This edge is truncated to a single point during
truncation and hence has at least one vertex $v$ that becomes degenerate. Let
$e^{\prime}$ be the other edge adjacent to $v$. If $e^{\prime}$ has length
greater than $2\delta$ then we charge $v$ to $e$. Otherwise we charge $v$ to
the edge that comes first along the respective curve. Say this is $e$. Note
that the other vertex $w$ of $e^{\prime}$ is also degenerate in $P^{\delta}$
or $Q^{\delta}$, so we charge $w$ to $e^{\prime}$ (which is the first edge
adjacent to $w$).

Since there are more than $n/\alpha$ edges of length at most $2\delta$, there
are more than $n/\alpha$ vertices that are degenerate in $P^{\delta}$ and
$Q^{\delta}$. After removing degenerate vertices, $P^{\delta}$ and
$Q^{\delta}$ have fewer than $n-n/\alpha$ vertices in total. In general, if
for some integer $k$, curves $P^{i\delta}$ and $Q^{i\delta}$ together have
more than $n/\alpha$ edges of length at most $2\delta$ for all $i\leq k$, then
$P^{(k+1)\delta}$ and $Q^{(k+1)\delta}$ have fewer than $n-kn/\alpha$ vertices
in total. It follows that there is an $\varepsilon=k\delta\leq\alpha\delta$
for which $P^{\varepsilon}$ and $Q^{\varepsilon}$ together have at most
$n/\alpha$ edges of length at most $2\delta$.

We now extend the truncated smoothing definition to higher-dimensional curves.
We define the truncated smoothing of a $d$-dimensional curve using a parameter
vector $\vec{\varepsilon}\in[0,\infty)^{d}$. The truncated
$\vec{\varepsilon}$-smoothing $P^{\vec{\varepsilon}}$ of a curve $P$ as the
result of coordinate-wise truncated smoothing with the corresponding elements
of $\vec{\varepsilon}$ as parameters. Under the $L_{\infty}$-norm, this
coordinate-wise procedure yields an error that is at most the maximum of the
errors obtained from the one-dimensional truncated smoothings. Note that every
monotone piece on a higher-dimensional curve $P$ projects onto (part of) a
single edge in every dimension. Thus if the number of edges of a certain
length $c$ in any projection is at most $k$, then there are at most $dk$
monotone pieces on $P$ that are $c$-narrow. We obtain the following theorem as
consequences of Lemmas 4.3 and 4.5.

######  Theorem 4.7.

Let $P$ and $Q$ be two $d$-dimensional curves with $n$ vertices. For all
$\alpha\in[1,n]$ and $\delta\geq 0$, there is a vector
$\vec{\varepsilon}\in[0,\delta\alpha]^{d}$ for which $P^{\vec{\varepsilon}}$
and $Q^{\vec{\varepsilon}}$ together have at most $dn/\alpha$ monotone pieces
that are $2\delta$-narrow. Furthermore, we have
$d_{F}(P^{\vec{\varepsilon}},Q^{\vec{\varepsilon}})\leq d_{F}(P,Q)\leq
d_{F}(P^{\vec{\varepsilon}},Q^{\vec{\varepsilon}})+2\alpha\delta$.

###  4.2 Constructing truncated smoothings

We present a linear time algorithm for constructing the truncated
$\varepsilon$-smoothing $P^{\varepsilon}$ of a one-dimensional curve $P$,
together with the parameterization induced by $P$. This immediately gives a
linear time algorithm for constructing truncated smoothings for higher-
dimensional curves. The parameterization of $P^{\varepsilon}$ is piecewise-
linear and its vertices correspond to the vertices of $P$. Hence it suffices
to compute the points $p^{\varepsilon}_{1},\dots,p^{\varepsilon}_{n}$ on
$P^{\varepsilon}$ that correspond to the vertices $p_{1},\dots,p_{n}$ of $P$.

The algorithm relies on computing the _death times_ of the vertices
$p_{1},\dots,p_{n}$ of $P$. We define the death time of a vertex $p_{i}$ of
$P$ to be the smallest value $\varepsilon\geq 0$ for which $p_{i}$ is
degenerate in $P^{\varepsilon}$ (and thus is removed for higher parameter
truncated smoothings). Note that the death times of $p_{1}$ and $p_{n}$ are
infinite, and that the death time of a degenerate vertex of $P$ is trivially
$0$. In the following we show how to compute the death times of non-degenerate
vertices in $O(n)$ total time.

We proceed to express the death time of a non-degenerate vertex in terms of
the extreme values in its sub- or superlevel set component. The _sublevel set_
of a point $p$ on $P$ is the set of points on $P$ with value at most $p$. The
_sublevel set component_ of $p$ is the connected component of its sublevel set
that contains $p$, see Figure 5. The _superlevel set component_ of $p$ is
defined symmetrically. For a local maximum $p_{i}$ of $P$, let $P^{-}$ be its
sublevel set component. We define the points $\ell_{i}$ and $r_{i}$ as
(global) minima on the prefix and suffix curves of $P^{-}$ that end and start
at $p_{i}$, respectively. We let
$m_{i}\coloneqq\min\\{|p_{i}-\ell_{i}|,|p_{i}-r_{i}|\\}$, see Figure 5. We
symmetrically define $P^{+}$ to be the superlevel set component of a local
minimum $p_{i}$ of $P$, and symmetrically define $\ell_{i}$ and $r_{i}$ in
terms of $P^{+}$. The definition of $m_{i}$ is the same as for local maxima.
For a degenerate vertex $p_{i}$ we set $m_{i}\coloneqq 0$. We show that the
death time of an interior vertex $p_{i}$ is equal to $m_{i}/2$.

Figure 5: (left) The sublevel set component of $p_{i}$, below the dashed line
segment. Points $\ell_{i}$ and $r_{i}$ are the minima of the left and right
parts of this component. (middle and right) The max-Cartesian tree built on
the vertex sequence of $P$.

######  Lemma 4.8.

For all $2\leq i\leq n-1$ the death time of vertex $p_{i}$ is equal to
$m_{i}/2$.

######  Proof 4.9.

For any degenerate vertex $p_{i}$ of $P$ we have $m_{i}=0$, which is trivially
the death time of $p_{i}$. For the rest of the proof, assume for ease of
exposition that $P$ contains no degenerate vertices. Let $p_{i}$ be a (non-
degenerate) vertex of $P$, and assume without loss of generality that it is a
local maximum. We distinguish between the case where $p_{i}$ is incident to a
shortest edge of $P$ and the case where no incident edge has the minimum
length.

First assume that $p_{i}$ is incident to a shortest edge $e$ of $P$. Without
loss of generality, we also assume that $e=\overline{p_{i-1}p_{i}}$. If $i=2$
then the death time of $p_{i}$ is $\lVert e\rVert/2$, as it coincides with
$p_{1}$ in the truncated $\left(\lVert e\rVert/2\right)$-smoothing of $P$ and
hence becomes degenerate. We have $\ell_{2}=p_{1}$ and $r_{2}\leq p_{3}\leq
p_{1}$, so $m_{2}=|p_{2}-p_{1}|=\lVert e\rVert$. Hence the death time of
$p_{2}$ is $m_{2}/2$.

If $i>2$ then by the fact that $e$ has the minimum length of any edge we
obtain that $p_{i-2}\geq p_{i}\geq p_{i-1}$ and $p_{i-1}\geq p_{i+1}$. The
$\varepsilon$-truncated smoothing of $P$, for $\varepsilon=\lVert e\rVert/2$,
truncates $e$ to the point $p_{i}-\varepsilon$, moves $p_{i-2}$ to
$p_{i-2}-\varepsilon\geq p_{i}-\varepsilon$ and moves $p_{i+1}$ to
$p_{i+1}+\varepsilon\leq p_{i-1}+\varepsilon=p_{i}-\varepsilon$. This means
that $p_{i}$ becomes degenerate, and thus its death time is
$\varepsilon=\lVert e\rVert/2$. We have $\ell_{i}=p_{i-1}$ and $r_{i}\leq
p_{i+1}\leq\ell_{i}$, hence $m_{i}=|p_{i}-\ell_{i}|=\lVert e\rVert$. See
Figure 5. Hence the death time of $p_{i}$ is $m_{i}/2$.

Next assume that $p_{i}$ is not incident to a shortest edge of $P$. Let
$\varepsilon$ be equal to half the minimum edge length of $P$. Note that
$\ell_{i}$ and $r_{i}$ are both local minima of $P$. As every local minimum of
$P$ gets increased by $\varepsilon$ by the simplification, every local maximum
gets decreased by $\varepsilon$, and the minimum edge length of $P$ is
$2\varepsilon$, we obtain that the points
$\ell^{\varepsilon}_{i}\coloneqq\ell_{i}+\varepsilon$ and
$r^{\varepsilon}_{i}\coloneqq r_{i}+\varepsilon$ are the analogues of
$\ell_{i}$ and $r_{i}$ for the point $p^{\varepsilon}_{i}$, with respect to
$P^{\varepsilon}$. It follows that $m^{\varepsilon}_{i}$, the analogue of
$m_{i}$, is equal to
$\min\\{|p^{\varepsilon}_{i}-\ell^{\varepsilon}_{i}|,|p^{\varepsilon}_{i}-r^{\varepsilon}_{i}|\\}=m_{i}-2\varepsilon$.
Applying the above recursively on the point $p^{\varepsilon}_{i}$, curve
$P^{\varepsilon}$ and value $m^{\varepsilon}_{i}$ shows that the death time of
$p_{i}$ is $m_{i}/2$.

With the expression for the death times of interior vertices, we are able to
compute the death times of these vertices in linear total time. To this end we
use _Cartesian trees_ , introduced by Vuillemin [26]. A Cartesian tree is a
binary tree with the heap property. We call a Cartesian tree a _max-Cartesian
tree_ if it has the max-heap property and a _min-Cartesian tree_ if it has the
min-heap property. A max-Cartesian tree $T$ for a sequence of values
$x_{1},\dots,x_{n}$ is recursively defined as follows. The root of $T$
contains the maximum value $x_{j}$ in the sequence. The subtree left of the
root node is a max-Cartesian tree for the sequence $x_{1},\dots,x_{j-1}$, and
the right subtree is a max-Cartesian tree for the sequence
$x_{j+1},\dots,x_{n}$ (see Figure 5). Min-Cartesian trees are defined
symmetrically.

######  Lemma 4.10.

We can compute the death time of every interior vertex in $O(n)$ time. The
death times are reported as the sequence $m_{2}/2,\dots,m_{n-1}/2$.

######  Proof 4.11.

To compute the death times we build two Cartesian trees; a max-Cartesian tree
$T_{\max}$ and a min-Cartesian tree $T_{\min}$, both built on the sequence of
vertices $p_{1},\dots,p_{n}$ of $P$. These trees can be constructed in $O(n)$
time [20].

For a given node $\nu$ of $T_{\max}$ storing vertex $p_{i}$, the vertices
stored in the subtree rooted at $\nu$ are precisely those in the sublevel set
component of $p_{i}$. Thus if $p_{i}$ is a local maximum, the values
$\ell_{i}$ and $r_{i}$ are precisely the minimum values stored in the left and
right subtrees of $\nu$, respectively. We can therefore compute the death
times of the interior local maxima of $P$ with a bottom-up traversal of
$T_{\max}$, taking $O(n)$ time. Repeating the above process for $T_{\min}$, we
compute the death times of the interior local minima of $P$ in $O(n)$ time as
well. The death times of degenerate vertices are set to $0$, regardless of the
values of $\ell_{i}$ and $r_{i}$.

We augment the respective trees during their traversals to store the death
times of vertices in the corresponding nodes. With in-order traversals of
$T_{\max}$ and $T_{\min}$, interleaving the steps so we traverse the nodes in
their order of index, we can construct the sequence of death times
$m_{2}/2,\dots,m_{n-1}/2$ in $O(n)$ time, rather than the $O(n\log n)$ time
required to sort the death times by index.

We construct the truncated $\varepsilon$-smoothing in linear time using a max-
Cartesian tree $T$ built on the sequence of death times reported by the
algorithm of Lemma 4.10 (see Figure 6). Since we do not compute
$p^{\varepsilon}_{1},\dots,p^{\varepsilon}_{n}$ in order of index, we augment
$T$ to store these values in the corresponding nodes. Afterwards we extract
$P^{\varepsilon}$ from $T$ with an in-order traversal, without needing to sort
the values based on index. This lowers the running time from $O(n\log n)$ to
$O(n)$.

Figure 6: (left) The truncated $\varepsilon$-smoothing for $\varepsilon=8$.
The curve has three non-degenerate vertices, corresponding to the three
vertices $p_{1}$, $p_{3}$ and $p_{9}$ with death times larger than
$\varepsilon$. The curve also indicates the location of degenerate vertices.
(right) The death times of the vertices, stored in a max-Cartesian tree.

First we compute $p^{\varepsilon}_{1}$ and $p^{\varepsilon}_{n}$, as $p_{1}$
and $p_{n}$ behave differently from the rest during the truncated smoothing
procedure. These vertices may change direction before their death time (which
is infinite), whereas others move in a single direction until they become
degenerate. To compute $p^{\varepsilon}_{1}$ (and symmetrically
$p^{\varepsilon}_{n}$), we simulate the truncated smoothing procedure, but
only for $p_{1}$. To this end we scan through the vertices of $P$.

Let $p_{i}$ be the current vertex and let $\varepsilon^{\prime}$ be the
current parameter. We keep track of the position of the first vertex
$p^{\varepsilon^{\prime}}_{1}$ and maintain the invariant that
$p^{\varepsilon^{\prime}}_{i}$ is the second non-degenerate vertex of
$P^{\varepsilon^{\prime}}$ (the first being $p^{\varepsilon^{\prime}}_{1}$).
Initially we set $p_{i}$ to the second non-degenerate vertex of $P$ and set
$\varepsilon^{\prime}\coloneqq 0$ and $p^{\varepsilon^{\prime}}_{1}\coloneqq
p_{1}$. Let $\varepsilon^{\prime\prime}$ be the death time of $p_{i}$. If
$\varepsilon\leq\varepsilon^{\prime\prime}$, then the value of
$p^{\varepsilon}_{1}$ is either
$p^{\varepsilon^{\prime}}_{1}-(\varepsilon-\varepsilon^{\prime})$ (if
$p^{\varepsilon^{\prime}}_{1}$ is a local maximum) or
$p^{\varepsilon^{\prime}}_{1}+(\varepsilon-\varepsilon^{\prime})$ (if
$p^{\varepsilon^{\prime}}_{1}$ is a local minimum). Otherwise, the value of
$p^{\varepsilon^{\prime\prime}}_{1}$ is
$p^{\varepsilon^{\prime}}_{1}-(\varepsilon-\varepsilon^{\prime})$ (if
$p^{\varepsilon^{\prime}}_{1}$ is a local maximum) or
$p^{\varepsilon^{\prime}}_{1}+(\varepsilon-\varepsilon^{\prime})$ (if
$p^{\varepsilon^{\prime}}_{1}$ is a local minimum). We set
$\varepsilon^{\prime}\coloneqq\varepsilon^{\prime\prime}$ and set
$p^{\varepsilon^{\prime}}_{1}$ to the above value. To set $p_{i}$ we continue
the scan of the vertices until we have reached the first vertex with a death
time greater than $\varepsilon^{\prime}$.

With the above procedure we compute $p^{\varepsilon}_{1}$ and
$p^{\varepsilon}_{n}$ in $O(n)$ time and store the values in the respective
nodes of $T$. Afterwards we compute the locations of the interior vertices of
$P^{\varepsilon}$ by traversing $T$. For this we use the following technical
lemma.

######  Lemma 4.12.

Let $p_{i}$ be an interior vertex of $P$ with death time at most
$\varepsilon$. Let $p_{\ell}$ and $p_{r}$ be the last vertex before $p_{i}$,
respectively the first vertex after $p_{i}$, with death times greater than
that of $p_{i}$. Then $p^{\varepsilon}_{i}$ is equal to the value on
$\overline{p^{\varepsilon}_{\ell}p^{\varepsilon}_{r}}$ closest to either
$p_{i}-m_{i}/2$ (if $p_{i}$ is a local maximum) or $p_{i}+m_{i}/2$ (if $p_{i}$
is a local minimum).

######  Proof 4.13.

Assume $p_{i}$ is a local maximum. The case when $p_{i}$ is a local minimum is
symmetric. Let $\varepsilon^{\prime}=m_{i}/2$ be the death time of $p_{i}$ and
let $p^{\varepsilon^{\prime}}_{1},\dots,p^{\varepsilon^{\prime}}_{n}$ be the
points on $P^{\varepsilon^{\prime}}$ corresponding to the vertices
$p_{1},\dots,p_{n}$ of $P$. The value of $p^{\varepsilon^{\prime}}_{i}$ is
equal to $p_{i}-\varepsilon^{\prime}$.

All points $p^{\varepsilon^{\prime}}_{j}$ of $P^{\varepsilon^{\prime}}$ with
$\ell<j<r$ are degenerate, as their death times are at most
$\varepsilon^{\prime}$. These points therefore do not move further during the
truncated smoothing procedure, unless they coincide with either
$p^{\varepsilon^{\prime\prime}}_{\ell}$ or
$p^{\varepsilon^{\prime\prime}}_{r}$ for some
$\varepsilon^{\prime}\leq\varepsilon^{\prime\prime}\leq\varepsilon$. It
follows that all these points lie on
$\overline{p^{\varepsilon}_{\ell}p^{\varepsilon}_{r}}$. Specifically,
$p^{\varepsilon}_{i}$ is equal to
$p^{\varepsilon^{\prime}}_{i}=p_{i}-m_{i}/2$, unless
$p^{\varepsilon^{\prime\prime}}_{i}$ coincides with either
$p^{\varepsilon^{\prime\prime}}_{\ell}$ or
$p^{\varepsilon^{\prime\prime}}_{r}$ for some
$\varepsilon^{\prime}\leq\varepsilon^{\prime\prime}\leq\varepsilon$, in which
case $p^{\varepsilon}_{i}$ is equal to $p^{\varepsilon}_{\ell}$, respectively
$p^{\varepsilon}_{r}$.

Note that the orientation of $p^{\varepsilon^{\prime\prime}}_{\ell}$ relative
to $p^{\varepsilon^{\prime\prime}}_{r}$ is the same for all
$\varepsilon^{\prime}\leq\varepsilon^{\prime\prime}$ (including the case where
the points coincide). This is because the points are consecutive non-
degenerate vertices for $\varepsilon^{\prime\prime}=\varepsilon^{\prime}$. To
change orientation the points must attain the same value at some point, and
since the subcurve between the points spans merely the line segment between
the points, the points coincide at this point. Thus if $p^{\varepsilon}_{i}$
is equal to either $p^{\varepsilon}_{i}$ or $p^{\varepsilon}_{\ell}$, then
this endpoint is the point closest to $p_{i}-m_{i}/2$.

With the above technical lemma we are ready to give the algorithm for
computing the interior vertices
$p^{\varepsilon}_{2},\dots,p^{\varepsilon}_{n-1}$ of $P^{\varepsilon}$. We
perform a pre-order traversal of $T$, during which we compute the value of
$p^{\varepsilon}_{i}$ once we get to the node $\nu_{i}$ storing vertex
$p_{i}$. During the traversal, we keep track of the nodes $\nu_{\ell}$ and
$\nu_{r}$ that store the last vertex before $p_{i}$, respectively the first
vertex after $p_{i}$. This is possible since $\nu_{\ell}$ and $\nu_{r}$ are
both ancestors of $\nu_{i}$, so we have already visited them during the
traversal. Since we have already visited them, we have also already computed
the values of $p^{\varepsilon}_{\ell}$ and $p^{\varepsilon}_{r}$. We compute
the value of $p^{\varepsilon}_{i}$ in constant time using Lemma 4.12 and
augment $\nu_{i}$ to store this value. Afterwards we extract $P^{\varepsilon}$
from $T$ with a single in-order traversal. This gives the following results.

######  Lemma 4.14.

We can construct the truncated $\varepsilon$-smoothing of a one-dimensional
curve with $n$ vertices in $O(n)$ time for any $\varepsilon\geq 0$.

######  Theorem 4.15.

We can construct the truncated $\vec{\varepsilon}$-smoothing of a
$d$-dimensional curve with $n$ vertices in $O(n)$ time for any vector
$\vec{\varepsilon}\in[0,\infty)^{d}$.

###  4.3 Finding the right parameter

Let $P$ and $Q$ again be our input curves with $n$ vertices, let $\delta\geq
0$ be our decision parameter and $\alpha\in[1,n]$ be the chosen approximation
factor. Recall from Theorem 4.7 that there is a parameter vector
$\vec{\varepsilon}\in[0,\alpha\delta/2]^{d}$ such that $P^{\vec{\varepsilon}}$
and $Q^{\vec{\varepsilon}}$ together have at most $dn/\alpha$ monotone pieces
that are $2\delta$-narrow. In this section, we show how to compute such a
parameter vector $\vec{\varepsilon}$ in $O(n)$ time.

Recall from Section 4.1 that it is sufficient to compute parameters
$\varepsilon_{i}$ for which the truncated $\varepsilon_{i}$-smoothings of the
projections of $P$ and $Q$ onto the $i^{\mathrm{th}}$ coordinate axis together
have at most $n/\alpha$ edges of length at most $2\delta$. We therefore abuse
notation slightly to let $P$ and $Q$ denote the projections of the curves onto
some coordinate axis, and we show how to compute a parameter $\varepsilon$
such that $P^{\varepsilon}$ and $Q^{\varepsilon}$ together have at most
$n/\alpha$ edges of length at most $2\delta$.

We use the death times of the vertices of $P$ and $Q$ (see Section 4.2). These
can be computed in $O(n)$ total time. Let $M$ be the multiset of death times
of the vertices of $P$ and $Q$. Any $\varepsilon$ for which the half-open
interval $(\varepsilon,\varepsilon+\delta]$ contains at most $n/\alpha$
elements of $M$ results in truncated smoothings $P^{\varepsilon}$ and
$Q^{\varepsilon}$ with at most $n/\alpha$ edges of length at most $2\delta$.
This is because each edge of length at most $2\delta$ in $P^{\varepsilon}$ and
$Q^{\varepsilon}$ is truncated to a point in the truncated $\delta$-smoothing
of these curves and hence contains a vertex with death time at most $\delta$,
which corresponds to a vertex of $P$ or $Q$ with death time at most
$\varepsilon+\delta$.

It suffices to look for an $\varepsilon\in M\cup\\{0\\}$, as any other value
$\varepsilon^{\prime}$ with at most $n/\alpha$ death times in
$(\varepsilon^{\prime}+\delta]$ implies that the highest value $\varepsilon\in
M\cup\\{0\\}$ below $\varepsilon^{\prime}$ has at most $n/\alpha$ death times
in $(\varepsilon+\delta]$. The following lemma helps us in searching for a
valid parameter $\varepsilon$, as it allows us to discard half the death times
of $M$ based on the median death time.

######  Lemma 4.16.

Let $m^{*}$ be the median of $M$. If $m^{*}>\alpha\delta/2$, then there exists
a half-open interval
$(\varepsilon,\varepsilon+\delta]\subseteq(0,\alpha\delta/2]$ that contains at
most $|M|/\alpha$ elements of $M$.

######  Proof 4.17.

Partition the interval $(0,\alpha\delta/2]$ into $\alpha/2$ disjoint half-open
intervals of length $\delta$. For sake of contradiction say that each of these
intervals has more than $n/\alpha$ elements of $M$ in it. Because the
intervals are disjoint, there are more than $|M|/2$ elements of $M$ in
$(0,\alpha\delta/2]$. The $(|M|/2)^{\mathrm{th}}$ death time, which is the
median $m^{*}$, is therefore at most $\alpha\delta/2$, giving a contradiction.

We proceed to give a recursive algorithm for computing a valid parameter
$\varepsilon\in M\cup\\{0\\}$. Specifically, the algorithm returns a value
$\varepsilon\coloneqq\varepsilon(M,\alpha)$ such that there are at most
$|M|/\alpha$ values of $M$ inside the interval
$(\varepsilon,\varepsilon+\delta]$. We first compute $m^{*}$ in $O(|M|)$ time
[4] and then proceed according to the following three cases.

  1. 1.

If $|M|\leq n/\alpha$ then $\varepsilon(M,\alpha)\coloneqq 0$ is a valid
parameter.

  2. 2.

If $m^{*}>\alpha\delta/2$ then by Lemma 4.16 there is a valid parameter
$\varepsilon\in[0,\alpha\delta/2-\delta]$. We limit our search to parameters
in this range, which means that all death times greater than $\alpha\delta/2$
can be discarded. We set $M^{\prime}\coloneqq\\{m\mid m\in
M,m\leq\alpha\delta/2\\}$ and return $\varepsilon(M^{\prime},\alpha/2)$.

  3. 3.

If $m^{*}\leq\alpha\delta/2$ then we limit our search to parameters greater
than $\alpha\delta/2$. To be able to do this through recursion we discard
death times that are at most $\alpha\delta/2$ and modify the remaining death
times to be $\alpha\delta/2$ smaller. We set
$M^{\prime}=\\{m-\alpha\delta/2\mid m\in M,m>\alpha\delta/2\\}$ and return
$\varepsilon(M^{\prime},\alpha/2)+\alpha\delta/2$.

The running time $T(M,\alpha)$ of the algorithm satisfies the recurrence

$T(M,\alpha)=\begin{cases}O(1)&\text{if $|M|\leq n/\alpha$,}\\\
T(M^{\prime})+O(|M|)&\text{otherwise,}\end{cases}$

where $|M^{\prime}|\leq|M|/2$. This recurrence implies that
$T(M,\alpha)=O(|M|)$ and hence the running time of the above algorithm is
$O(n)$. The value of the returned parameter $\varepsilon(M,\alpha)$ satisfies
the recurrence

$\varepsilon(M,\alpha)\leq\begin{cases}0&\text{if $|M|\leq n/\alpha$,}\\\
\varepsilon(M^{\prime},\alpha/2)+\alpha\delta/2&\text{otherwise,}\end{cases}$

where again $|M^{\prime}|\leq|M|/2$. This recurrence implies that
$\varepsilon\coloneqq\varepsilon(M,\alpha)\leq\alpha\delta$. We obtain the
following result.

######  Theorem 4.18.

Let $P$ and $Q$ be two $d$-dimensional curves with $n$ vertices. Let
$\alpha\in[1,n]$ and $\delta\geq 0$. In $O(n)$ time, we can compute a vector
$\vec{\varepsilon}\in[0,\alpha\delta]^{d}$ for which $P^{\vec{\varepsilon}}$
and $Q^{\vec{\varepsilon}}$ together have at most $dn/\alpha$ monotone pieces
that are $2\delta$-narrow.

##  5 A faster algorithm in one dimension

Next we present an $O(n\log^{2}n+(n^{2}/\alpha^{3})\log n\log\log n)$ time
algorithm for deciding if a matching exists that is constrained to lie within
$O(n/\alpha)$ cells of the diagonal. We assume this is the case for $P$ and
$Q$, which can be achieved in linear time with the simplification of Section 4
(giving an additive $2\alpha$ term in the approximation factor). This
algorithm is a great improvement over the state-of-the-art algorithm by van
der Horst et al. [25], who achieve a running time of
$O(n\log^{3}n+(n^{2}/\alpha)\log^{3}n)$.

The algorithm uses a subroutine for constructing approximate exit sets. The
_$\delta$ -exit set_ for a set of points $S\subseteq\\{0\\}\times[0,1]$ with
respect to $P$ and $Q$ is the set of all points
$E(S)\subseteq\\{1\\}\times[0,1]$ that are $\delta$-reachable from points in
$S$. We allow for approximations, where instead of constructing an (exact)
$\delta$-exit set for $S$, we construct an _$(\alpha,\delta)$ -exit set_
$E_{\alpha}(S)$. Such a set must contain all of $E(S)$, and may only contain
points that are $\alpha\delta$-reachable from points in $S$. We prove the
following theorem in Section 6:

######  Theorem 5.1.

Let $P$ and $Q$ be two one-dimensional curves with $n$ vertices. For any
$\alpha\geq 1$ and $\delta\geq 0$, we can construct an $(\alpha,\delta)$-exit
set $E_{\alpha}(S)$ for a given set $S\subseteq\\{0\\}\times[0,1]$ consisting
of $O(n)$ connected components in $O(n\log^{2}n+(n^{2}/\alpha^{2})\log
n\log\log n)$ time.

Since matchings are restricted to lie within $K=2n/\alpha+1$ cells of the free
space diagonal, the total complexity of the reachable free space is only
$O(n^{2}/\alpha)$, rather than potentially quadratic. We wish to translate
this lower complexity into lower input complexities for subroutines. For this
we cover the reachable free space with $\alpha$ interior-disjoint rectangles,
each $K\times 3K$ cells in dimension, such that rectangles do not share a
common $x$-coordinate on their interiors. That is, the rectangles are laid out
from left to right over the reachable free space. See Figure 7 for an
illustration.

Figure 7: (left) Matchings are constrained to within $K$ cells of the
diagonal. (middle) The $\alpha$ rectangles covering all possible matchings.
Each rectangle spans $K$ cells in width and $3K$ cells in height. (right)
Constructing exit sets in each rectangle, given the exit set of the previous
rectangle.

We iteratively go over the rectangles from left to right, constructing exit
sets inside each rectangle for given sets on their left boundary. Let
$R_{1},\dots,R_{\alpha}$ be the rectangles in left to right order. Let
$P_{1},\dots,P_{\alpha}$ be the subcurves of $P$ corresponding to these
rectangles, and let $Q_{1},\dots,Q_{\alpha}$ be the subcurves of $Q$
corresponding to these rectangles. For each rectangle $R_{i}$ we construct an
$(\alpha,\delta)$-exit set $E_{i}=E_{\alpha}(S_{i})$ for the set
$S_{i}=E_{i-1}\cap\mathcal{F}_{\leq\delta}(P,Q)$, with respect to $P_{i}$ and
$Q_{i}$. We construct these exit sets using the algorithm of Section 6.

Initially, $S_{1}=\\{(0,0)\\}$. Given a set $S_{i}$, we construct $E_{i}$
using Theorem 5.1 to construct an $(\alpha,\delta)$-exit set
$E_{\alpha}(S_{i})$ with respect to $P_{i}$ and $Q$. Because $P_{i}$ and
$Q_{i}$ have only $O(K)$ vertices each, we construct $E_{i}$ in
$O(K\log^{2}K+(K^{2}/\alpha^{2})\log K\log\log K)$ time. We then construct the
set $S_{i+1}$ as the intersection between $E_{i}$ and
$\mathcal{F}_{\leq\delta}(P_{i},Q_{i})$, which takes $O(K\log K)$ time by
sorting the sets and scanning over them.

Performing the above for all $\alpha$ rectangles, with $K=O(n/\alpha)$, we
obtain an $O(n\log^{2}n+(n^{2}/\alpha^{3})\log n\log\log n)$ time
$\alpha$-approximate decision algorithm, assuming that any $\delta$-matching
lies within $O(n/\alpha)$ cells from the diagonal. This assumption becomes
valid after the truncated smoothings of Section 4, which may incur an error of
$2\alpha$, resulting in an overall $3\alpha$-approximate decider.

######  Theorem 5.2.

Let $P$ and $Q$ be two one-dimensional curves with $n$ vertices. For any
$\alpha\geq 1$ and $\delta\geq 0$, we can decide whether $d_{F}(P,Q)\leq
3\alpha\delta$ or $d_{F}(P,Q)>\delta$ in $O(n\log^{2}n+(n^{2}/\alpha^{3})\log
n\log\log n)$ time.

To turn this decision algorithm into an approximation algorithm for the
Fréchet distance, we apply the black box technique of Colombe and Fox [15].
For any $\varepsilon\in(0,1]$, this increases the running time by a factor
$\log(n/\varepsilon)$ and the approximation factor by a factor
$(1+\varepsilon)$. We set $\varepsilon=1$ for concreteness, giving an
$O(n\log^{3}n+(n^{2}/\alpha^{3})\log^{2}n\log\log n)$ time
$6\alpha$-approximation algorithm for the Fréchet distance. To turn this
algorithm into an $\alpha$-approximation algorithm running in the same time
bound, we set $\alpha\leftarrow\alpha/6$ for $\alpha\geq 6$, and run the exact
quadratic time decision algorithm of Alt and Godau [2] for $\alpha\in[1,6)$.
This gives the following result:

######  Theorem 5.3.

Let $P$ and $Q$ be two one-dimensional curves with $n$ vertices. For any
$\alpha\geq 1$, we can compute an $\alpha$-approximation to $d_{F}(P,Q)$ in
$O(n\log^{3}n+(n^{2}/\alpha^{3})\log^{2}n\log\log n)$ time.

##  6 Constructing approximate exit sets

In this section we present an algorithm for efficiently constructing
approximate exit sets for one-dimensional curves $P$ and $Q$ with $n$
vertices. In Section 6.1 we first present a data structure for constructing
approximate exit sets for sets of the form $\\{0\\}\times[y_{1},y_{2}]$ when
$P$ is a line segment. Then in Section 6.2 we extend this data structure to
construct exit sets for when $P$ is a “good” curve. Finally, in Section 6.3 we
use this data structure to construct exit sets for the general case, where we
construct exit sets for general sets of points, making no assumptions on $P$.

###  6.1 Exit sets for single line segments

First we give an algorithm for constructing an $(\alpha,\delta)$-exit sets for
sets of the form $\\{0\\}\times[y_{1},y_{2}]$, with respect to a directed line
segment $e$ and the curve $Q$. The construction takes $O(\log n\log\log n)$
time, after preprocessing $Q$ in $O(n\log^{2}n)$ time. The quality of the
resulting approximate exit set depends on the diameter of $Q[y_{1},y_{2}]$.
Specifically, let its diameter be $D\delta$. Then the returned set is a
$(3D+9,\delta)$-exit set.

Let $Q(y^{\prime}_{1})$ be the first point on $Q[y_{1},1]$ within distance
$\delta$ of $e(1)$. Either 1) $y^{\prime}_{1}\in[y_{1},y_{2}]$ or 2)
$y^{\prime}_{1}\in(y_{2},1]$. In case 1), all of $Q[y_{1},y_{2}]$ lies within
distance $(D+1)\delta$ of $e(1)$. This implies that any subcurve
$Q[y,y^{\prime}]$ with $y\in[y_{1},y_{2}]$ and
$d_{F}(e,Q[y,y^{\prime}])\leq\delta$ also lies within distance $(D+1)\delta$
of $e(1)$. The maximum interval $[y,y^{\prime}]$ for which $Q[y,y^{\prime}]$
has this property corresponds to a $(D+1,\delta)$-exit set for points in
$\\{0\\}\times[y_{1},y_{2}]$. See Figure 8 (left).

Figure 8: The two types of constructed exit set. The purple points are
$Q(y^{\prime}_{1})$. Left is the case where $y^{\prime}_{1}\in[y_{1},y_{2}]$,
right is the case where $y^{\prime}_{1}\in(y_{2},1]$. The green regions are
the exit sets.

We report this interval, and with that a $(D+1,\delta)$-exit set in case 1),
in $O(\log n\log\log n)$ time using the data structure of Lemma 6.1:

######  Lemma 6.1.

We can preprocess $Q$ in $O(n)$ time, such that given values $\varepsilon\geq
0$ and $y\in[0,1]$, as well as a point $p$, we can report the first point
$Q(y_{1})$ within distance $\varepsilon$ of $p$, with $y_{1}\in[y,1]$, in
$O(\log n\log\log n)$ time. Additionally, we can report the maximal interval
$[y_{1},y_{2}]$ for which $Q[y_{1},y_{2}]$ lies completely within distance
$\varepsilon$ of $p$ in the same asymptotic time bound.

######  Proof 6.2.

We construct a balanced binary search tree $T$ on the vertices of $Q$, ordered
based on appearance along $Q$. This tree takes $O(n)$ time to construct,
considering the vertices of $Q$ are pre-sorted by traversing $Q$. Each node of
$T$ stores the convex hull of its canonical subset of vertices. For an
internal node, the convex hull can be computed in constant time once the
convex hulls of its child nodes are known. Hence with a depth-first search, we
compute all these convex hulls in $O(n)$ additional time.

To query $T$ for the first point on $Q[y,1]$ that is within distance $\delta$
of $p$, we perform binary search over the vertices of $Q[y,1]$, using $T$ to
guide the search. During the search, we keep track of the convex hull of the
current subcurve $Q[y,y^{\prime}]$. Rather than constructing this hull from
scratch every time, we keep track of the minimum and maximum of the hull with
a binary min- and max-heap. These heaps contain the minima, respectively
maxima, of the convex hulls stored in all nodes along the search path. Because
there are only $O(\log n)$ values in these heaps at any time, constructing the
convex hull of $Q[y,y^{\prime}]$ takes only $O(\log\log n)$ time. At every
step of the binary search, we add or remove only one hull from the heaps,
taking $O(\log\log n)$ time as well. Hence a step takes $O(\log\log n)$ time.

After $O(\log n)$ steps, taking a total of $O(\log n\log\log n)$ time, we have
two consecutive vertices $Q(y^{\prime}_{1}),Q(y^{\prime}_{2})$ with $p$ being
within distance $\varepsilon$ of the convex hull of $Q[y,y^{\prime}_{2}]$, but
not of $Q[y,y^{\prime}_{1}]$. The first point $Q(y_{1})$ within distance
$\varepsilon$ of $p$ thus is the first point on
$\overline{Q(y^{\prime}_{1})Q(y^{\prime}_{2})}$ within distance $\varepsilon$
of $p$.

Given $y_{1}$, we compute the maximal interval $[y_{1},y_{2}]$ for which
$Q[y_{1},y_{2}]$ lies completely within distance $\varepsilon$ of $p$ in a
similar manner. Compute two consecutive vertices
$Q(y^{\prime}_{1}),Q(y^{\prime}_{2})$ the convex hull of
$Q[y_{1},y^{\prime}_{1}]$ being completely within distance $\varepsilon$ of
$p$, but with the convex hull of $Q[y_{1},y^{\prime}_{2}]$ containing a point
with distance greater than $\varepsilon$ to $p$. The last point on
$\overline{Q(y^{\prime}_{1})Q(y^{\prime}_{2})}$ that is within distance
$\varepsilon$ of $p$ corresponds to the value $y_{2}$.

For case 2), consider a subcurve $Q[y,y^{\prime}]$ with $y\in[y_{1},y_{2}]$
and $d_{F}(e,Q[y,y^{\prime}])\leq\delta$ (if one exists) and let $\varphi$ be
an arbitrary $\delta$-matching between the curves. Gudmundsson et al. [22]
observe that $Q[y^{\prime}_{1},y^{\prime}]$ must lie completely within
distance $3\delta$ of $e(1)$.333 Gudmundsson et al.show the propery for
segments of length greater than $2\delta$, but the statement naturally holds
for shorter segments as well.  Hence the maximal interval
$[y^{\prime}_{1},y^{\prime}_{2}]$ with $Q[y^{\prime}_{1},y^{\prime}_{2}]$
completely within distance $3\delta$ of $e(1)$ contains all possible values
$y^{\prime}$ for which $d_{F}(e,Q[y,y^{\prime}])\leq\delta$. We report this
interval with the data structure of Lemma 6.1.

In case 2), the interval $[y^{\prime}_{1},y^{\prime}_{2}]$ corresponds to an
$(D+3)$-approximate exit set for points in $\\{0\\}\times[y_{1},y_{2}]$, if a
non-empty exit set exists. In order for a non-empty exit set to exist, it must
be the case that $d_{F}(e,Q[y_{1},y^{\prime}_{2}])\leq(D+3)\delta$. We use the
following data structure by Driemel and Har-Peled [16] to approximately decide
whether this is the case.

######  Lemma 6.3 ([16, Theorem 5.6]).

We can preprocess $Q$ in $O(n\log^{2}n)$ time, such that given an interval
$[y_{1},y_{2}]\subseteq[0,1]$ and a directed line segment $e$, we can compute
a $3$-approximation to $d_{F}(e,Q[y_{1},y_{2}])$ in $O(\log n\log\log n)$
time.

Recently, Buchin et al. [11] gave a data structure for querying the exact
Fréchet distance between a subcurve of $Q$ and a query segment. Their data
structure has the same preprocessing time, $O(n\log^{2}n)$, but a higher query
time, $O(\log^{2}n)$. Since approximating by a constant factor gives only a
constant factor increase in total approximation ratio, which can be negated by
a constant factor increase in running time, we opt for the approximation data
structure. If desired, the approximation ratio of the data structure can be
made arbitrarily close to $1$, at the cost of preprocessing and query times.

With the above data structure we compute a $3$-approximation to
$d_{F}(e,Q[y_{1},y^{\prime}_{2}])$. If the returned value is at most
$(3D+9)\delta$, we conclude that
$d_{F}(e,Q[y_{1},y^{\prime}_{2}])\leq(3D+9)\delta$, and otherwise we conclude
that $d_{F}(e,Q[y_{1},y^{\prime}_{2}])\geq(D+3)\delta$.

The total time taken to construct and decide whether to report
$[y^{\prime}_{1},y^{\prime}_{2}]$ is $O(\log n\log\log n)$ in both cases. The
preprocessing time is $O(n\log^{2}n)$. We thus obtain the following:

######  Lemma 6.4.

We can preprocess $Q$ in $O(n\log^{2}n)$ time, such that given a directed line
segment $e$ and an interval $[y_{1},y_{2}]$, we can report a
$(3D+9,\delta)$-exit set for $\\{0\\}\times[y_{1},y_{2}]$ in $O(\log n\log\log
n)$ time, where $D\delta$ is the diameter of $Q[y_{1},y_{2}]$. The reported
exit set is of the form $\\{1\\}\times[y^{\prime}_{1},y^{\prime}_{2}]$ with
$Q[y^{\prime}_{1},y^{\prime}_{2}]$ completely within distance $3\delta$ of
$e(1)$.

###  6.2 Exit sets for interior-good subcurves

In this section we extend the data structure of Section 6.1 to efficiently
construct exit sets for singleton sets $\\{(0,y)\\}$ with respect to
“interior-good” subcurves of $P$, rather than mere line segments. We define
what good subcurves are in Section 6.2.1, showing a useful property regarding
the Fréchet distance. Then we use this property in Section 6.2.2 to construct
exit sets for interior-good curves.

####  6.2.1 Good curves

First we make the observation that even though we are working in the
continuous setting, the possible matchings are all relatively discrete. For
this we make use of _$\delta$ -signatures_, introduced by Driemel et al. [18].
The $\delta$-signature $\Sigma_{\delta}(P)$ of a one-dimensional curve $P$ is
the curve defined by the series of values $0=s_{1}<\dots<s_{k}=1$ with the
following properties:

  1. 1.

(non-degeneracy) For all $2\leq i\leq k-1$:
$P(s_{i})\notin\overline{P(s_{i-1})P(s_{i+1})}$.

  2. 2.

(direction-preserving) For all $1\leq i\leq k-1$:
If $P(s_{i})<P(s_{i+1})$, then for all $s,s^{\prime}\in[s_{i},s_{i+1}]$ with
$s<s^{\prime}$, $P(s)-P(s^{\prime})\leq 2\delta$.
If $P(s_{i})>P(s_{i+1})$, then for all $s,s^{\prime}\in[s_{i},s_{i+1}]$ with
$s<s^{\prime}$, $P(s^{\prime})-P(s)\leq 2\delta$.

  3. 3.

(minimum edge length) For all $2\leq i\leq k-2$:
$|P(s_{i+1})-P(s_{i})|>2\delta$.
$|P(s_{2})-P(s_{1})|>\delta$ and $|P(s_{k})-P(s_{k-1})|>\delta$.

  4. 4.

(range) For all $s\in[s_{i},s_{i+1}]$ with $1\leq i\leq k-1$:
If $2\leq i\leq k-2$, then $P(s)\in\overline{P(s_{i})P(s_{i+1})}$.
If $i=1$ and $k>2$, then
$P(s)\in\overline{P(s_{1})P(s_{2})}\cup[P(s_{1})-\delta,P(s_{1})+\delta]$.
If $i=k-1$ and $k>2$, then
$P(s)\in\overline{P(s_{k-2}P(s_{k-1})}\cup[P(s_{k-1})-\delta,P(s_{k-1})+\delta]$.
If $i=1$ and $k=2$, then
$P(s)\in\overline{P(s_{1})P(s_{2})}\cup[P(s_{1})-\delta,P(s_{1})+\delta]\cup[P(s_{2})-\delta,P(s_{2})+\delta]$.

The first and fourth properties imply that the parameters $s_{i}$ specify
vertices of $P$. We refer to these vertices as the _$\delta$ -signature
vertices_ of $P$.

######  Lemma 6.5.

Any $\delta$-matching between one-dimensional curves $P$ and $Q$ matches
$\delta$-signature vertices of $P$ to points on edges of $Q$ with an endpoint
within distance $\delta$.

######  Proof 6.6.

Van der Horst et al. [25] proved a generalization of the statement, though
here we give a more concise proof. Let $\sigma_{1},\dots,\sigma_{k}$ be the
$\delta$-signature vertices of $P$. Fix a $\delta$-matching $\varphi$ between
$P$ and $Q$. By definition of the Fréchet distance, $\varphi$ matches
$\sigma_{1}$ to $Q(0)$ and $\sigma_{k}$ to $Q(1)$, making the statement hold
immediately for these signature vertices. Next consider a signature vertex
$\sigma_{i}$, for some $1<i<k$. Assume that
$\sigma_{i-1}<\sigma_{i}>\sigma_{i+1}$ (the other case is symmetric and hence
omitted). Let $Q(x_{i-1}),\leavevmode\nobreak\ Q(x_{i}),\leavevmode\nobreak\
Q(x_{i+1})$ be the points on $Q$ matched to $\sigma_{i-1},\leavevmode\nobreak\
\sigma_{i}$ and $\sigma_{i+1}$, respectively. It follows from the range
property that $Q[x_{i-1},x_{i+1}]$ lies completely left of
$\sigma_{i}+\delta$. Hence the edge of $Q$ containing $Q(x_{i})$, which is
also an edge of $Q[x_{i-1},x_{i+1}]$, must have an endpoint in
$[Q(x_{i}),\sigma_{i}+\delta]\subseteq[\sigma_{i}-\delta,\sigma_{i}+\delta]$.

With the above observation, continuous matchings can be seen as (almost)
discrete when restricted to signature vertices of one of the curves. We use
this to apply ideas of the algorithm for the discrete Fréchet distance by Chan
and Rahmati [13].

Their main idea is to identify bad vertices. Consider an infinite grid
$\mathbb{G}$ with cellwidth $\alpha\delta$. A point $p$ is _$c$ -bad_, for
some $c\geq 0$, if it is within $c\delta$ of the boundary of $\mathbb{G}$.
Points that are not $c$-bad are referred to as _$c$ -good_. See Figure 9.

Figure 9: The real line $\mathbb{R}$ partitioned into gridcells of size
$\alpha\delta$. On the top line the $c$-bad points are shown in red and the
$c$-good points in green. On the bottom line the gridcells are labelled.

A curve $P$ is $c$-good if all its vertices are $c$-good.

Curves with good signatures have a particularly useful property, linking the
Fréchet distance to exact string matching. We assume that no vertex of either
curve lies on the boundary of $\mathbb{G}$, which can be achieved by an
infinitesimal shift of the curves without affecting the distances between
points. We assign unique integer labels to the gridcells, through some order-
preserving bijection from $\mathbb{Z}$, and let $\ell(v)$ denote the label of
the gridcell containing a vertex $v$. The _label curve_ of a curve $P$ with
vertices $p_{1},\dots,p_{n}$ is the continuous curve with vertices
$\ell(p_{1}),\dots,\ell(p_{n})$. The main property linking the Fréchet
distance to exact string matching is given in Lemma 6.9. To prove this lemma,
we use the concept of _visiting orders_ , introduced by Bringmann et al. [6].
A _$\delta$ -visiting order_ of a curve $P$ with vertices $p_{1},\dots,p_{n}$
on some curve $Q$ with vertices $q_{1},\dots,q_{m}$ is a sequence of indices
$j_{1}\leq\dots\leq j_{n}$ such that $|p_{i}-q_{j_{i}}|\leq\delta$ for all
$i$. We use the following results on signatures and visiting orders (rephrased
as done in [6]):

######  Lemma 6.7 ([18, Lemma 3.1]).

For any $\delta\geq 0$ and curve $P$ we have
$d_{F}(P,\Sigma_{\delta}(P))\leq\delta$.

######  Lemma 6.8 ([18, Lemma 3.2]).

For any $\delta\geq 0$ and curves $P$ and $Q$ with $d_{F}(P,Q)\leq\delta$,
there exists a $\delta$-visiting order of $\Sigma_{\delta}(P)$ on $Q$.

######  Lemma 6.9.

Let $P$ be a curve whose $\delta$-signature is $5$-good and let $Q$ be an
arbitrary curve. If $d_{F}(P,Q)\leq\delta$ then the label curves of
$\Sigma_{\delta}(P)$ and the $\Sigma_{2\delta}(Q)$ are equal (up to
reparameterization). Conversely, if the label curves of $\Sigma_{\delta}(P)$
and the $\Sigma_{2\delta}(Q)$ are equal, then
$d_{F}(P,Q)\leq(\alpha+3)\delta$.

######  Proof 6.10.

Let $\ell_{1},\dots,\ell_{k}$ be the extrema of the label curve of
$\Sigma_{\delta}(P)$. These labels correspond to subcurves
$\Sigma_{1},\dots,\Sigma_{k}$ inside the corresponding gridcells. Note that
these subcurves do not combine to make $\Sigma_{\delta}(P)$, since we ignore
labels that are not extreme. We make use of the following claim:

######  Claim 1.

Every $\Sigma_{i}$ contains a $3\delta$-signature vertex of $P$.

The case where $i\in\\{1,k\\}$ holds trivially. Hence assume that $1<i<k$.
Further assume without loss of generality that
$\ell_{i-1},\ell_{i+1}<\ell_{i}$. The curve $\Sigma_{i}$ starts and ends on
the left boundary of the cell with label $\ell_{i}$, staying inside this cell.
Let $\sigma$ be a rightmost vertex of $\Sigma_{i}$. We assume for ease of
exposition that this vertex is unique. By definition $\sigma$ is a
$\delta$-signature vertex. We show that $\sigma$ is also a $3\delta$-signature
vertex.

Suppose for a contradiction that $\sigma$ is not a $3\delta$-signature vertex.
By the range property, there are $3\delta$-signature vertices
$\sigma_{j},\sigma_{j+1}$ of $P$ with $\sigma$ on the subcurve between them
and $\sigma\in\overline{\sigma_{j}\sigma_{j+1}}$. Since we assumed the
rightmost vertex of $\Sigma_{i}$ to be unique, both $\sigma_{j}$ and
$\sigma_{j+1}$ cannot be interior to $\Sigma_{i}$, as otherwise the range
property would be violated by one of the endpoints of $\Sigma_{i}$. However,
this violates the direction-preserving property. This is because the subcurve
between $\sigma_{j}$ and $\sigma_{j+1}$ must have edges crossing the left
boundary of cell $\ell_{i}$, once from left to right and once from right to
left. These edges must both have a length greater than $10\delta$, as they
cross an interval of length $10\delta$ around the boundary where no vertices
of $\Sigma_{\delta}(P)$ lie. Therefore $\sigma$ must be a $3\delta$-signature
vertex of $P$.

By Lemmas 6.7 and 6.8 there is a $3\delta$-visiting order of
$\Sigma_{3\delta}(P)$ on $\Sigma_{2\delta}(Q)$. By 1 every $\Sigma_{i}$
contains a $3\delta$-signature vertex of $P$. Recall that these vertices are
$5$-good. Hence the $3\delta$-visiting order implies that there is a sequence
of $2\delta$-signature vertices $\tau_{1},\dots,\tau_{k}$ of $Q$ with each
$\tau_{i}$ lying in the same gridcell as $\Sigma_{i}$. All of these vertices
are $2$-good, because every $\delta$-signature vertex of $P$ is $5$-good.

By Lemmas 6.7 and 6.8 there is also a $2\delta$-visiting order of
$\Sigma_{2\delta}(Q)$ on $\Sigma_{\delta}(P)$. This, together with the fact
that each $\tau_{i}$ is $2$-good, implies that there is a sequence of
$\delta$-signature vertices
$\sigma^{\prime}_{1},\dots,\sigma^{\prime}_{k^{\prime}}$ of $P$ with each
$\sigma^{\prime}_{i}$ lying inside the same gridcell as $\tau_{i}$. The
extrema defined by these gridcells are equal to the extrema of the label curve
of $\Sigma_{\delta}(P)$, meaning the label curves of $\Sigma_{\delta}(P)$ and
the $\Sigma_{2\delta}(Q)$ are the same (up to reparameterization).

Next suppose that the label curves of $\Sigma_{\delta}(P)$ and
$\Sigma_{2\delta}(Q)$ are equal. We show that
$d_{F}(P,Q)\leq(\alpha+3)\delta$. For this, we construct an
$\alpha\delta$-matching between $\Sigma_{\delta}(P)$ and $\Sigma_{2\delta}(Q)$
by matching points on $\Sigma_{\delta}(P)$ to points on $\Sigma_{2\delta}(Q)$
inside the same gridcell. This matching naturally has cost at most
$\alpha\delta$, and by the triangle inequality and Lemma 6.7 we get
$d_{F}(P,Q)\leq
d_{F}(P,\Sigma_{\delta}(P))+d_{F}(\Sigma_{\delta}(P),\Sigma_{2\delta}(Q))+d_{F}(\Sigma_{2\delta}(Q),Q)\leq(\alpha+3)\delta$.

####  6.2.2 Exit sets for interior good subcurves

Next we give a data structure for constructing approximate exit sets for
“interior-good” subcurves of $P$. We call a subcurve $P^{\prime}$ of $P$
interior $c$-good if all interior vertices of its $\delta$-signature are
$c$-good.

Let $P^{\prime}=P[s_{i-1},s_{j+1}]$ be an interior $6$-good subcurve. Given a
point $z=(0,y)\in\mathcal{F}_{\leq\delta}(P^{\prime},Q)$, we show through a
construction that there exists a $(3\alpha/2+11,\delta)$-exit set
$E_{3\alpha/2+11}(\\{z\\})$ consisting of a single connected component. This
construction can be performed in $O(\log n\log\log n)$ time, after having
preprocessed $P$ and $Q$ into data structures in $O(n\log^{2}n)$ time.

Let $P(s_{i}),P(s_{j})$ be the first, respectively last, $\delta$-signature
vertices on the interior of $P^{\prime}$, and let
$P^{\prime}(s^{\prime}_{i})=P(s_{i})$ and
$P^{\prime}(s^{\prime}_{j})=P(s_{j})$. We first construct an approximate exit
set for $\\{z\\}$ with respect to $P^{\prime}[0,s^{\prime}_{i}]$ and $Q$. For
this, note that because $P^{\prime}[0,s^{\prime}_{i}]=P[s_{i-1},s_{i}]$ is the
subcurve between two consecutive signature vertices, we have
$d_{F}(P^{\prime}[0,s^{\prime}_{i}],\overline{P^{\prime}(0)P^{\prime}(s^{\prime}_{i})})\leq\delta$
by Lemma 6.7. We construct a $(9,2\delta)$-exit set for $\\{z\\}$ with respect
to $\overline{P^{\prime}(0)P^{\prime}(s^{\prime}_{i})}$ and $Q$ with the data
structure of Lemma 6.4. Note that the returned exit set is of the form
$\\{1\\}\times[y_{1},y_{2}]$, where $Q[y_{1},y_{2}]$ is completely within
distance $6\delta$ of $P^{\prime}(s^{\prime}_{i})$. Observe that the returned
exit set is also a $(19,\delta)$-exit set with respect to
$P^{\prime}[0,s^{\prime}_{i}]$ and $Q$. Indeed, any partial $\delta$-matching
between $P^{\prime}[0,s^{\prime}_{i}]$ and $Q$ is also a partial
$2\delta$-matching between
$\overline{P^{\prime}(0)P^{\prime}(s^{\prime}_{i})}$ and $Q$, so the exit set
contains all $\delta$-reachable points. Conversely, any $18\delta$-matching
between $\overline{P^{\prime}(0)P^{\prime}(s^{\prime}_{i})}$ and $Q$ is also a
$19\delta$-matching between $P^{\prime}[0,s^{\prime}_{i}]$ and $Q$, so the
exit set contains only $19\delta$-reachable points.

Next we extend the above exit set into one with respect to
$P^{\prime}[0,s^{\prime}_{j}]$ and $Q$. Because
$P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}]$ is $6$-good, we have by Lemma 6.9
that the label curves of
$\Sigma_{\delta}(P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}])$ and
$\Sigma_{2\delta}(Q[y,y^{\prime}])$ are the same for any subcurve
$Q[y,y^{\prime}]$ within Fréchet distance $\delta$ of
$P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}]$ Moreover, if the label curves of
$\Sigma_{\delta}(P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}])$ and
$\Sigma_{2\delta}(Q[y,y^{\prime}])$ are equal for some subcurve
$Q[y,y^{\prime}]$, then
$d_{F}(P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}],Q[y,y^{\prime}])\leq(\alpha+3)\delta$.
Observe that for any $y\in[y_{1},y_{2}]$, the label curves of all
$Q[y,y^{\prime}]$ are equal, since $Q[y_{1},y_{2}]$ lies within distance
$6\delta$ of $P^{\prime}(s^{\prime}_{i})$ and hence lies inside a single
gridcell. Therefore, taking the maximal subcurve
$Q[y^{\prime}_{1},y^{\prime}_{2}]$ such that the label curves of all
$\Sigma_{2\delta}(Q[y,y^{\prime}])$ with $y\in[y_{1},y_{2}]$ and
$y^{\prime}\in[y^{\prime}_{1},y^{\prime}_{2}]$ are equal to that of
$\Sigma_{\delta}(P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}])$, results in an
$(\alpha+3)$-approximate exit set for all points in
$\\{0\\}\times[y_{1},y_{2}]$.

We show how to construct such an exit set with the following data structure in
constant time:

######  Lemma 6.11.

We can preprocess $P$ and $Q$ in $O(n)$ time, such that given a subcurve
$P^{\prime}$ of $P$ and a value $y\in[0,1]$, we can report the interval
$[y_{1},y_{2}]$ such that $\Sigma_{\delta}(P^{\prime})$ and
$\Sigma_{2\delta}(Q[y,y^{\prime}])$ have the same label curves for any
$y^{\prime}\in[y_{1},y_{2}]$ in constant time.

######  Proof 6.12.

We make use of the string matching data structure of Chan and Rahmati [13].
They show that after preprocessing two strings in linear time, any two
substrings can be checked for equality in constant time. The strings we
preprocess are those defined by the extrema of the label curves of
$\Sigma_{\delta}(P)$ and $\Sigma_{2\delta}(Q)$. Constructing these signatures
(and their label curves) takes $O(n)$ time [18].

Let $A$ and $B$ be the strings defined by the label curves of
$\Sigma_{\delta}(P)$ and $\Sigma_{2\delta}(Q)$, respectively. Let
$A[x_{1},x_{2}]$ be the substring of $A$ defined by extrema of the label curve
of $P$ corresponding to $\delta$-signature vertices on $P[x_{1},x_{2}]$.
Define $B[y_{1},y_{2}]$ analogously. For a given query subcurve
$P[x_{1},x_{2}]$, the extrema of the label curve of
$\Sigma_{\delta}(P^{\prime})$ define the string $\ell(P(x_{1}))\circ
A[x_{1},x_{2}]\circ\ell(P(x_{2}))$, with consecutive duplicate characters
removed. This affects only the first and last characters in $A[x_{1},x_{2}]$.
Symmetrically, given a value $y$, a subcurve $Q[y,y^{\prime}]$ defines the
string $\ell(Q(y))\circ B[y,y^{\prime}]\circ\ell(Q(y^{\prime}))$, with
consecutive duplicate characters. This also affects only the first and last
characters in $B[y_{1},y_{2}]$.

We perform three tests, with which we determine the interval $[y_{1},y_{2}]$
containing all $y^{\prime}$ for which the label curves of $\Sigma_{\delta}(P)$
and $\Sigma_{2\delta}(Q[y,y^{\prime}])$ are equal. We first test whether
$\ell(P(x_{1}))=\ell(Q(y))$ by comparing the labels in constant time. We
define $A^{\prime}$ to be the maximal substring of $A[x_{1},x_{2}]$ that does
not start at $\ell(P(x_{1}))$ and does not end at $\ell(P(x_{2}))$. Because
the length of $A^{\prime}$ is fixed, there is only one possible substring
$B^{\prime}$ of $B$ that can match to it. Specifically, this is the substring
of length $|A^{\prime}|$ starting at the character after $\ell(Q(y))$. We test
if $A^{\prime}=B^{\prime}$ in constant time. Lastly, we test if
$\ell(P(x_{2}))=\ell(Q(y^{\prime}))$. If any of these tests fail, then there
is no $y^{\prime}$ for which $\Sigma_{\delta}(P)$ and
$\Sigma_{2\delta}(Q[y,y^{\prime}])$ have the same label curves. Otherwise, the
maximum interval $[y_{1},y_{2}]$ containing $y^{\prime}$ for which
$Q[y_{1},y_{2}]$ lies inside cell $\ell(P(x_{2}))$ meets the query
requirements. This range can be obtained from the parameterization of $B$ in
constant time.

The above gives an $(\alpha+3,\delta)$-exit set
$\\{1\\}\times[y^{\prime}_{1},y^{\prime}_{2}]$ for all points in
$\\{0\\}\times[y_{1},y_{2}]$, with respect to
$P^{\prime}[s^{\prime}_{i},s^{\prime}_{j}]$ and $Q$. This exit set is also an
$(\alpha+3,\delta)$-exit set for $\\{z\\}$, with respect to
$P^{\prime}[0,s^{\prime}_{j}]$ and $Q$.

Finally, we extend the exit set to be an exit set for $\\{z\\}$ with respect
to all of $P^{\prime}$ and $Q$. The diameter of
$Q[y^{\prime}_{1},y^{\prime}_{2}]$ is at most $\alpha\delta$, since it lies
inside a single gridcell. Similar to the first exit set, note that because
$P^{\prime}[s^{\prime}_{j},1]=P[s_{j},s_{j+1}]$ is the subcurve between two
consecutive signature vertices, we have
$d_{F}(P^{\prime}[s^{\prime}_{j},1],\overline{P^{\prime}(s^{\prime}_{j})P^{\prime}(1)})\leq\delta$
by Lemma 6.7. We construct a $(3\alpha/2+9,2\delta)$-exit set for
$\\{0\\}\times[y^{\prime}_{1},y^{\prime}_{2}]$ with respect to
$\overline{P^{\prime}(s^{\prime}_{j})P^{\prime}(1)}$ and $Q$, with the data
structure of Lemma 6.4. The returned exit set is also a
$(3\alpha+19,\delta)$-exit set with respect to $P^{\prime}[s^{\prime}_{j},1]$
and $Q$. By construction, the exit set is a $(3\alpha+19,\delta)$-exit set for
$\\{z\\}$ with respect to $P^{\prime}$ and $Q$. Lemma 6.13 follows.

######  Lemma 6.13.

We can preprocess $P$ and $Q$ in $O(n\log^{2}n)$ time, such that given an
interior $6$-good subcurve $P^{\prime}$ of $P$ and a point $z=(0,y)$, we can
report a $(3\alpha+19,\delta)$-exit set for $\\{z\\}$ with respect to
$P^{\prime}$ and $Q$ in $O(\log n\log\log n)$ time. The exit set consists of a
single connected component.

###  6.3 Constructing exit sets in the general case

We extend the result of Lemma 6.13 to the general case, where we wish to
construct an $(\alpha,\delta)$-exit set $E_{\alpha}(S)$ for a given set
$S\subseteq\\{0\\}\times[0,1]$ with respect to $P$ and $Q$, making no
assumptions on $P$. We do make the assumption that $S$ consists of only $O(n)$
connected components. This assumption holds for example for
$\mathcal{F}_{\leq\delta}(P,Q)\cap\\{0\\}\times[0,1]$, and thus is a natural
assumption to make. The algorithm takes $O(n\log^{2}n+(n^{2}/\alpha^{2})\log
n\log\log n)$ time, roughly matching the current state-of-the-art for the
discrete Fréchet distance [13] (although our algorithm is only for the one-
dimensional case). We assume $\alpha\geq 22$, to make expressions involving
$\alpha$ hold. For $\alpha\in[1,22)$ we can traverse the entire free space in
$O(n^{2})$ time, which is faster than the above bound for these values of
$\alpha$.

We first bound the number of $6$-bad $\delta$-signature vertices of $P$ and
$7$-bad vertices of $Q$. The total number of $c$-bad points on $P$ and $Q$ can
of course be $\Theta(n)$. However, Chan and Rahmati [13] show that by shifting
the curves it is always possible to reduce the number of $c$-bad points to at
most $cn/\alpha$, and show that such a shift can be computed in $O(n)$ time.
Hence we assume that the total number of $6$-bad $\delta$-signature vertices
of $P$, and $7$-bad vertices of $Q$, is $O(n/\alpha)$. This is achieved by
computing a shift with at most $7\cdot 2n/\alpha=O(n/\alpha)$ $7$-bad vertices
on both curve combined.

With the fact that every $\delta$-signature vertex of $P$ matches close to
vertices of $Q$ (see Lemma 6.5), we have that the $6$-bad $\delta$-signature
vertices of $P$ match to points on edges of $Q$ with a $7$-bad endpoint. Hence
these $6$-bad signature vertices have only $O(n/\alpha)$ possible edges to
match to. We use these vertices as “bottlenecks” in the free space, and we
compute exit sets between bottlenecks. The subcurves between these bottlenecks
are interior $6$-good, allowing us to use the data structure of Lemma 6.13 for
efficiently constructing exit sets.

We identify the $6$-bad $\delta$-signature vertices
$\sigma_{i_{1}},\dots,\sigma_{i_{k}}$ of $P$, and let
$s_{i_{1}},\dots,s_{i_{k}}$ be the values determining these vertices. The
possible edges a signature vertex can match to correspond to certain
_candidate passages_ in free space. We report these passages in $O(\log
n+n/\alpha)$ time, after $O(n\log n)$ time preprocessing, by storing the
vertices of $Q$ in a balanced binary search tree ordered by value, and
performing a range reporting query to report those vertices, and their
incident edges, close to the signature vertex.

We iteratively go through the $6$-bad $\delta$-signature vertices of $P$. For
each vertex $\sigma_{i_{j}}$, we construct an $(\alpha,\delta)$-exit set
$E_{j}=E_{\alpha}(S_{j})$ with respect to $P[s_{i_{j}},s_{i_{j+1}}]$ and $Q$,
given the set $S_{j}$ that is the intersection between $E_{j-1}$ and the
candidate passages of $\sigma_{i_{j}}$. We consider both $P(0)$ and $P(1)$ to
be $6$-bad, even if they are not, and let $\sigma_{i_{0}}=P(0)$ and
$\sigma_{i_{k+1}}=P(1)$. We also set $S_{0}=S$.

Suppose we have constructed a set $S_{j}$ and need to construct a set $E_{j}$.
For each connected component $\\{s_{i_{j}}\\}\times[y_{1},y_{2}]$ in $S_{j}$,
we construct an $(\alpha,\delta)$-exit set $E_{\alpha}(\\{(0,y_{1})\\})$ with
respect to $P[s_{i_{j}},s_{i_{j+1}}]$ and $Q$. Because
$P[s_{i_{j}},s_{i_{j+1}}]$ is interior $6$-good, this takes only $O(\log
n\log\log n)$ time with the algorithm of Lemma 6.13 (setting
$\alpha\leftarrow(\alpha-19)/3$). Furthermore, $E_{\alpha}(\\{(0,y_{1})\\})$
consists of a single connected component. We let $E_{j}=E_{\alpha}(S_{j})$ be
the union of all constructed exit sets, which we can construct in
$O(|S_{j-1}|\log n\log\log n)$ time by sorting the endpoints and scanning.
This is $O(n\log n\log\log n)$ for $j=1$ and $O((n/\alpha)\log n\log\log n)$
for all other $j$.

If $j=k$, then $E_{j}$ is an $(\alpha,\delta)$-exit set for $S_{0}=S$ (with
respect to $P$ and $Q$) and we are done. Otherwise, we turn $E_{j}$ into a
suitable set $S_{j+1}$ and repeat the process for $E_{j+1}$. To turn $E_{j}$
into $S_{j+1}$, we intersect $E_{j}$ with the union of the $O(n/\alpha)$
candidate passages of $\sigma_{j+1}$. We report these passages in $O(\log
n+n/\alpha)$ time, after which we construct their union in $O((n/\alpha)\log
n)$ time by sorting the endpoints of the passages. Using a single scan, the
intersection of the two sets can be computed in $O(n/\alpha)$ time, to obtain
$S_{j+1}$ in $O((n/\alpha)\log n\log\log n)$ time in total.

Because $k=O(n/\alpha)$, the above construction is repeated $O(n/\alpha)$
times and Theorem 5.1 follows.

See 5.1

##  7 An alternative approximation algorithm

Finally, we improve upon the state-of-the-art algorithm by van der Horst et
al. [25] for the approximate continuous Fréchet distance, by reducing the
running time by a logarithmic factor.

We use the simplification of Section 4 to reduce the number of
$2\delta$-narrow monotone pieces on both $P$ and $Q$ to at most $dn/\alpha$,
which by Theorem 3.1 makes the reachable free space constrained to within
$O(n/\alpha)$ blocks of the diagonal. This gives an additive $2\alpha$ term in
the approximation factor. We use the data structure of Corollary 7.3 for
traversing the free space inside a block.

######  Lemma 7.1.

We can preprocess a $d$-dimensional curve $P$ with $n$ vertices in $O(n)$
time, such that given a monotone piece $P_{i}$ of $P$ and line segment $e$ we
can compute the $\delta$-close points on the bottom and top sides of
$\mathcal{D}(P_{i},e)$ in $O(\log n)$ time.

######  Proof 7.2.

We store the vertices of each monotone piece $P_{i}$ in a binary search tree
$T_{i}$. Together with $T_{i}$ we store for each coordinate whether $P_{i}$
moves in the positive or negative direction, cutting ties arbitrarily.
Preprocessing $P$ takes $O(n)$ time, since the vertices are sorted after
scanning over $P$.

Given a monotone piece $P_{i}$ and query line segment $e$, we compute the
$\delta$-close points on the bottom and top sides of $\mathcal{D}(P_{i},e)$ by
computing the at most two maximal subcurves of $P_{i}$ that are within
distance $\delta$ of the endpoints of $e$. The subcurve close to the first
endpoint of $e$ corresponds to the $\delta$-close points on the bottom side of
$\mathcal{D}(P_{i},e)$, while the other subcurve corresponds to the
$\delta$-close points on the top side.

Let $q$ be an endpoint of $e$ and let $R$ be the axis-parallel hypercube
centered at $q$ with diameter $\delta$. Since we know the direction of
$P_{i}$, we can apply binary search over the vertices of $P_{i}$ to find the
first and last vertices of $P_{i}$ inside $R$. With $T_{i}$ this takes
$O(\log|P_{i}|)$ time. Computing the maximal subcurve inside $R$ takes
constant additional time, as we merely have to compare the edges incident to
the reported vertices with the boundary of $R$. Thus after
$O(\log|P_{i}|)=O(\log n)$ time, we have computed the subcurve of $P_{i}$ that
is within distance $\delta$ of $q$, which corresponds to the $\delta$-close
points on the bottom and top sides of $\mathcal{D}(P_{i},e)$.

By preprocessing $P$ and $Q$ separately as above, we can efficiently traverse
the free space within a block $B_{i,j}$ from bottom to top by iteratively
considering the edges of $Q_{j}$ together with all of $P_{i}$. We can traverse
$B_{i,j}$ from left to right in a symmetric manner. This leads to the
following result.

######  Corollary 7.3.

We can preprocess $P$ and $Q$ in $O(n)$ time, such that given a block
$B_{i,j}$ and all $\delta$-reachable points on the bottom and left sides of
$B_{i,j}$, represented by two horizontal and vertical line segments, we can
compute all $\delta$-reachable points on the top and right sides of $B_{i,j}$
in $O((|P_{i}|+|Q_{j}|)\log n)$ time.

By Theorem 3.1 each monotone piece of $P$ and $Q$ corresponds to only
$O(n/\alpha)$ blocks containing parts of the reachable free space. Using the
data structure of Corollary 7.3 to traverse these blocks, we get a free space
traversal algorithm with running time

$O\Big{(}(n/\alpha)\cdot\Big{[}\sum_{i}|P_{i}|+\sum_{j}|Q_{j}|\Big{]}\log
n\Big{)}=O((n^{2}/\alpha)\log n).$

This is summarized in Theorem 7.4.

######  Theorem 7.4.

Let $P$ and $Q$ be two $d$-dimensional curves with $n$ vertices. Let
$\alpha\geq 1$ and $\delta\geq 0$. We can decide whether
$d_{F}(P,Q)\leq(1+2\alpha)\delta$ or $d_{F}(P,Q)>\delta$ in
$O(n+(n^{2}/\alpha)\log n)$ time.

To turn this decision algorithm into an approximation algorithm for the
Fréchet distance, we apply the black box technique of Colombe and Fox [15].
For any $\varepsilon\in(0,1]$, this increases the running time by a factor
$\log(n/\varepsilon)$ and the approximation factor by a factor
$(1+\varepsilon)$. We set $\varepsilon=1$ for concreteness, giving an $O(n\log
n+(n^{2}/\alpha)\log^{2}n)$ time $(2+4\alpha)$-approximation algorithm for the
Fréchet distance. To turn this algorithm into an $\alpha$-approximation
algorithm running in the same time bound, we set
$\alpha\leftarrow(\alpha-2)/4$ for $\alpha\geq 6$, and run the exact quadratic
time decision algorithm of Alt and Godau [2] for $\alpha\in[1,6)$. This gives
the following result:

######  Theorem 7.5.

Let $P$ and $Q$ be two $d$-dimensional curves with $n$ vertices. For any
$\alpha\geq 1$ we can compute an $\alpha$-approximation to $d_{F}(P,Q)$ in
$O(n\log n+(n^{2}/\alpha)\log^{2}n)$ time.

##  8 Concluding remarks

We presented faster approximation algorithms for computing the continuous
Fréchet distance between curves. For the one-dimensional case in particular,
our algorithm significantly improves upon previous results. Our curve
simplification procedure proves to be a valuable tool in speeding up the one-
dimensional algorithm, and we are confident that future approximation
algorithms can make use of the simplification as well.

While we used the simplification for curves in general dimensions, lowering
the complexity of the reachable free space by a factor $\alpha$ (in terms of
blocks), we have not been able to take advantage of this lower complexity with
the existing result of van der Horst et al. [25]. Instead, we currently
traverse this lower-complexity space somewhat naively. We expect that our one-
dimensional algorithm can be adapted to work in higher dimensions as well,
taking advantage of the lower complexity to yield a faster algorithm. The main
hurdle is the time required to compare two “good” subcurves. In one dimension
this takes merely constant time using string matching. In higher dimensions
however, where we define a curve as good if the endpoints of all its monotone
pieces are good, we currently see no sublinear time algorithm for this, even
after preprocessing. The problem here is that a monotone piece may increase
the complexity of the label curve beyond linear, and obtaining a linear bound
even when approximations are allowed seems challenging.

## References

  * [1] Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, and Micha Sharir.  Computing the discrete Fréchet distance in subquadratic time.  SIAM Journal on Computing, 43(2):429–449, 2014.  doi:10.1137/130920526.
  * [2] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  International Journal of Computational Geometry & Applications, 5:75–91, 1995.  doi:10.1142/S0218195995000064.
  * [3] Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk.  Fréchet distance for curves, revisited.  In Proc. 14th Annual European Symposium on Algorithms (ESA), pages 52–63, 2006.  doi:10.1007/11841036\\_8.
  * [4] Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan.  Time bounds for selection.  Journal of Computer and System Sciences, 7(4):448–461, 1973.  doi:10.1016/S0022-0000(73)80033-9.
  * [5] Karl Bringmann.  Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails.  In Proc. 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 661–670, 2014.  doi:10.1109/FOCS.2014.76.
  * [6] Karl Bringmann, Anne Driemel, André Nusser, and Ioannis Psarros.  Tight bounds for approximate near neighbor searching for time series under the Fréchet distance.  In Proc. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 517–550. SIAM, 2022.  doi:10.1137/1.9781611977073.25.
  * [7] 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(1-2):85–120, 2017.  doi:10.1142/S0218195917600056.
  * [8] Karl Bringmann and Wolfgang Mulzer.  Approximability of the discrete Fréchet distance.  Journal of Computational Geometry, 7(2):46–76, 2016.  doi:10.20382/jocg.v7i2a4.
  * [9] Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer.  Four soviets walk the dog: Improved bounds for computing the Fréchet distance.  Discrete & Computational Geometry, 58(1):180–216, 2017.  doi:10.1007/s00454-017-9878-7.
  * [10] Kevin Buchin, Tim Ophelders, and Bettina Speckmann.  SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2887–2901, 2019.  doi:10.1137/1.9781611975482.179.
  * [11] Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals.  Efficient Fréchet distance queries for segments.  In Proc. 30th Annual European Symposium on Algorithms (ESA), pages 29:1–29:14, 2022.  doi:10.4230/LIPIcs.ESA.2022.29.
  * [12] Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders.  A family of metrics from the truncated smoothing of Reeb graphs.  In Proc. 37th International Symposium on Computational Geometry (SoCG), pages 22:1–22:17, 2021.  doi:10.4230/LIPIcs.SoCG.2021.22.
  * [13] Timothy M. Chan and Zahed Rahmati.  An improved approximation algorithm for the discrete Fréchet distance.  Information Processing Letters, 138:72–74, 2018.  doi:10.1016/j.ipl.2018.06.011.
  * [14] Lei Chen, M. Tamer Özsu, and Vincent Oria.  Robust and fast similarity search for moving object trajectories.  In Proc. 31st ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 491–502, 2005.  doi:10.1145/1066157.1066213.
  * [15] Connor Colombe and Kyle Fox.  Approximating the (continuous) Fréchet distance.  In Proc. 37th International Symposium on Computational Geometry (SoCG), pages 26:1–26:14, 2021.  doi:10.4230/LIPIcs.SoCG.2021.26.
  * [16] Anne Driemel and Sariel Har-Peled.  Jaywalking your dog: Computing the Fréchet distance with shortcuts.  SIAM Journal on Computing, 42(5):1830–1866, 2013.  doi:10.1137/120865112.
  * [17] 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, 2012.  doi:10.1007/s00454-012-9402-z.
  * [18] Anne Driemel, Amer Krivosija, and Christian Sohler.  Clustering time series under the Fréchet distance.  In Proc. 27th Annual Symposium on Discrete Algorithms (SODA), pages 766–785, 2016.  doi:10.1137/1.9781611974331.ch55.
  * [19] Thomas Eiter and Heikki Mannila.  Computing discrete Fréchet distance.  Technical report, Vienna University of Technology, 1994.
  * [20] Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan.  Scaling and related techniques for geometry problems.  In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 135–143, 1984.  doi:10.1145/800057.808675.
  * [21] Michael Godau.  A natural metric for curves - computing the distance for polygonal chains and approximation algorithms.  In Proc. 8th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 127–136, 1991.  doi:10.1007/BFb0020793.
  * [22] Joachim Gudmundsson, Majid Mirzanezhad, Ali Mohades, and Carola Wenk.  Fast Fréchet distance between curves with long edges.  International Journal of Computational Geometry & Applications, 29(2):161–187, 2019.  doi:10.1142/S0218195919500043.
  * [23] Xiao-Ying Liu and Chuan-Lun Ren.  Fast subsequence matching under time warping in time-series databases.  In Proc. 12th International Conference on Machine Learning and Cybernetics (ICML), pages 1584–1590, 2013.  doi:10.1109/ICMLC.2013.6890855.
  * [24] Mario E. Munich and Pietro Perona.  Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification.  In Proc. 7th International Conference on Computer Vision (ICCV), pages 108–115, 1999.  doi:10.1109/ICCV.1999.791205.
  * [25] Thijs van der Horst, Marc J. van Kreveld, Tim Ophelders, and Bettina Speckmann.  A subquadratic _n_ ${}^{\mbox{{$\varepsilon$}}}$-approximation for the continuous Fréchet distance.  In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1759–1776, 2023.  doi:10.1137/1.9781611977554.ch67.
  * [26] Jean Vuillemin.  A unifying look at data structures.  Communications of the ACM, 23(4):229–239, 1980.  doi:10.1145/358841.358852.