# Fréchet Distance in Subquadratic Time††thanks: Research supported by
Research Grants Council, Hong Kong, China (project no. 16208923).

Siu-Wing Cheng111Department of Computer Science and Engineering, HKUST, Hong
Kong. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Haoqiang
Huang22footnotemark: 2

Let $m$ and $n$ be the numbers of vertices of two polygonal curves in
$\mathbb{R}^{d}$ for any fixed $d$ such that $m\leq n$. Since it was known in
1995 how to compute the Fréchet distance of these two curves in
$O(mn\log(mn))$ time, it has been an open problem whether the running time can
be reduced to $o(n^{2})$ when $m=\Omega(n)$. In the mean time, several well-
known quadratic time barriers in computational geometry have been overcome:
3SUM, some 3SUM-hard problems, and the computation of some distances between
two polygonal curves, including the discrete Fréchet distance, the dynamic
time warping distance, and the geometric edit distance. It is curious that the
quadratic time barrier for Fréchet distance still stands. We present an
algorithm to compute the Fréchet distance in $O(mn(\log\log n)^{2+\mu}\log
n/\log^{1+\mu}m)$ expected time for some constant $\mu\in(0,1)$. It is the
first algorithm that returns the Fréchet distance in $o(mn)$ time when
$m=\Omega(n^{\varepsilon})$ for any fixed $\varepsilon\in(0,1]$.

##  1 Introduction

Measuring the similarity between two curves is a fundamental task in many
applications such as moving object analysis [14] and road network
reconstruction [13]. Fréchet distance is a popular distance metric for curves
as it captures their similarity well [3].

Let $\tau=(v_{1},v_{2},...,v_{n})$ be a polygonal curve in $\mathbb{R}^{d}$. A
_parameterization_ $\rho$ of $\tau$ maps every $t\in[0,1]$ to a point
$\rho(t)$ on $\tau$ such that $\rho(0)=v_{1}$, $\rho(1)=v_{n}$, and $\rho(t)$
moves monotonically from $v_{1}$ to $v_{n}$ as $t$ increases from 0 to 1. Let
$\varrho$ be a parameterization of another polygonal curve
$\sigma=(w_{1},w_{2},...,w_{m})$. The pair $(\rho,\varrho)$ define a
_matching_ $\mathcal{M}$ that maps $\rho(t)$ with $\varrho(t)$ for all
$t\in[0,1]$. A point in $\tau$ may have multiple matching partners in $\sigma$
and vice versa. Let $d(x,y)$ be the Euclidean distance between $x$ and $y$ in
$\mathbb{R}^{d}$. The distance between $\tau$ and $\sigma$ realized by
$\mathcal{M}$ is
$d_{\mathcal{M}}(\tau,\sigma)=\max_{t\in[0,1]}d(\rho(t),\varrho(t))$. The
_Fréchet distance_ $d_{F}(\sigma,\tau)$ between $\sigma$ and $\tau$ is
$\inf_{\mathcal{M}}d_{\mathcal{M}}(\tau,\sigma)$. We call a matching that
realizes the Fréchet distance a _Fréchet matching_. If we restrict each
parameterization to match a vertex of $\tau$ to at least one vertex of
$\sigma$, and vice versa, the resulting
$\inf_{\mathcal{M}}d_{\mathcal{M}}(\tau,\sigma)$ is known as the _discrete
Fréchet distance_ , which we denote by $\tilde{d}_{F}(\sigma,\tau)$. It
follows from the definition that
$d_{F}(\sigma,\tau)\leq\tilde{d}_{F}(\sigma,\tau)$.

We assume throughout this paper that $m\leq n$. Godau [26] described the first
polynomial-time algorithm for computing $d_{F}(\sigma,\tau)$ that runs in
$O\bigl{(}(nm^{2}+n^{2}m)\log(mn)\bigr{)}$ time. Alt and Godau [4] improved
the running time to $O(mn\log(mn))$ in their seminal work [4]. Eiter and
Mannila [23] showed that the discrete Fréchet distance can be computed in
$O(mn)$ time by a simple dynamic programming algorithm. For roughly two
decades, these running times remained state-of-the-art, and the quadratic time
barrier stood unbroken.

Agarwal et al. [2] eventually broke the barrier for $\tilde{d}_{F}$ in
$\mathbb{R}^{2}$ in 2013 and gave an algorithm that runs in $O(mn\log\log
n/\log n)$-time on a word RAM machine with $\Theta(\log n)$ word size. They
asked whether one can extend this result to compute $d_{F}$ in subquadratic
time. Buchin et al. [15] developed a faster _randomized_ algorithm for
computing $d_{F}$ in $\mathbb{R}^{2}$ that takes $O\bigl{(}mn\sqrt{\log
n}(\log\log n)^{3/2}\bigr{)}$ expected time on a pointer machine and
$O\bigl{(}mn(\log\log n)^{2}\bigr{)}$ expected time on a word RAM machine of
$\Theta(\log n)$ word size. Blank and Driemel [8] presented an algorithm in
one dimension that computes $d_{F}$ in $O(m^{2}\log^{2}n+n\log n)$ time, which
is subquadratic when $m=o(n)$.

Bringmann proved two important negative results in $\mathbb{R}^{d}$ for $d\geq
2$ [9]. First, the widely accepted _Strong Exponential Time Hypothesis_ (SETH)
would be refuted if there is a _strongly subquadratic_ algorithm for $d_{F}$
or $\tilde{d}_{F}$, i.e., a running time of
$O\bigl{(}(mn)^{1-\varepsilon}\bigr{)}$ for any fixed $\varepsilon\in(0,1)$.
Second, no strongly subquadratic algorithm can approximate $d_{F}$ within a
factor $1.001$ unless SETH fails. Later, Bringmann and Mulzer [11] proved that
no strongly subquadratic algorithm can approximate $\tilde{d}_{F}$ within a
factor 1.399 even in $\mathbb{R}$ unless SETH fails. Buchin et al. [16] showed
that no strongly subquadratic algorithm can approximate $d_{F}$ within a
factor 3 even in $\mathbb{R}$ unless SETH fails.

On the positive side, assuming that $m=n$, Bringmann and Mulzer [11] presented
an $O(\alpha$)-approximation algorithm for $\tilde{d}_{F}$ that runs in
$O(n\log n+n^{2}/\alpha)$ time for any $\alpha\in[n]$. Chan and Rahmati [18]
improved the running time to $O(n\log n+n^{2}/\alpha^{2})$ for any
$\alpha\in[1,\sqrt{n/\log n}]$. Later, assuming that $m=n$, Colombe and Fox
[20] showed an $O(\alpha)$-approximation algorithm for $d_{F}$ that runs in
$O((n^{3}/\alpha^{2})\log n)$ time for any $\alpha\in[\sqrt{n},n]$. There is a
recent improvement by Van der Horst et al. [34]: assuming that $m\leq n$,
there is an $O(\alpha)$-approximation algorithm for $d_{F}$ that runs in
$O((n+mn/\alpha)\log^{3}n)$ time for any $\alpha\in[1,n]$. More recently, the
running time has been improved to $O((n+mn/\alpha)\log^{2}n)$ by Van der Horst
and Ophelders [33]. In all, for any fixed $\varepsilon\in(0,1]$, there are
strongly subquadratic $n^{\varepsilon}$-approximation algorithms for $d_{F}$
and $\tilde{d}_{F}$. There are better results for some restricted classes of
input curves [5, 6, 10, 21, 30].

It is curious that the quadratic time barrier for $d_{F}$ still stands because
several quadratic time barriers in computational geometry have been overcome,
including 3SUM and some 3SUM-hard problems [17, 25, 27, 29, 31], the
computation of the discrete Fréchet distance [2], and the computation of the
dynamic time warping and geometric edit distances [28]; in particular, the
works in [2, 28] are about distances between polygonal curves. In this paper,
we give a subquadratic-time algorithm that computes $d_{F}$ in
$\mathbb{R}^{d}$ for any fixed $d$. We use the real RAM model in which a word
can store a real number or an integer/pointer of $O(\log n)$ bits. We assume
that standard arithmetic operations can be performed in $O(1)$ time on real
numbers and integers. We also assume that one can use an integer of $O(\log
n)$ bits to do a table lookup in $O(1)$ time. Similar computation models have
been used in [17, 28]. About the word RAM model used in [2, 15], the authors
also exploit the constant-time table lookup capability only without using bit
operations.

For any fixed $d$, our algorithm computes $d_{F}(\sigma,\tau)$ in
$\mathbb{R}^{d}$ in $O(mn(\log\log n)^{2+\mu}\log n/\log^{1+\mu}m)$ expected
time for some constant $\mu\in(0,1)$. This is the first algorithm that runs in
$o(mn)$ time when $m=\Omega(n^{\varepsilon})$ for some fixed
$\varepsilon\in(0,1]$. Computing $d_{F}$, $\tilde{d}_{F}$, and the dynamic
time warping distance reduces to filling a two-dimensional dynamic programming
table. We start with the Four-Russians trick that groups cells of the tables
into boxes and batch the processing of boxes; this approach has been applied
successfully to speed up the computation of $\tilde{d}_{F}$ and the dynamic
time warping distance. It involves encoding different configurations of these
boxes during dynamic programming.

Our first contribution is using algebraic geometric tools to prove that the
number of distinct encodings is subquadratic which is the cornerstone of our
result. Nevertheless, this bound does not lead to a subquadratic-time
algorithm for computing $d_{F}$ yet due to the continuous nature of $d_{F}$.
Our second contribution is a second level of batch processing that clusters
the boxes to save the time for information transfer among the boxes within a
cluster. This two-level strategy gives a decision algorithm that runs in
$O(mn(\log\log n)^{2+\mu}/\log^{1+\mu}m)$ expected time for some constant
$\mu\in(0,1)$. It is faster than the decision algorithm by Buchin et al. [15]
for the word RAM model.

Alt and Godau [4, Theorem 6] showed that if there is a decision procedure that
runs in $T(n)$ time, one can compute $d_{F}(\sigma,\tau)$ in $O(T(n)\log(mn))$
time. Hence, our decision procedure implies that one can compute
$d_{F}(\sigma,\tau)$ in $O(mn(\log\log m)^{2+\mu}\log n/\log^{1+\mu}m)$
expected time. Algebraic geometric tools have recently been applied to some
Fréchet and Hausdorff distance problems, including range searching, VC
dimension, curve simplification, nearest neighbor, and distance oracle [1, 12,
19, 22]. This paper lends further support to the versatility of this framework
for curve proximity problems.

##  2 Background

For any two points $p,q\in\tau$, if $p$ does not appear behind $q$ along
$\tau$, we use $\tau[p,q]$ to denote the subcurve of $\tau$ from $p$ to $q$.
We use $pq$ to denote the oriented line segment from $p$ to $q$.

###  2.1 Fréchet distance

The key concept in determining $d_{F}(\sigma,\tau)$ is the _reachability
interval_ [4]. Take a point $x\in\tau$ and a point $y\in\sigma$. The pair
$(x,y)$ is _reachable_ with respect to $\delta$ if and only if
$d_{F}(\tau[v_{1},x],\sigma[w_{1},y])\leq\delta$. The reachability intervals
of $x$ include all points in $\sigma$ that can form reachable pairs with $x$.
The reachability intervals of $y$ are defined analogously.

Any point $x\in\tau$ or $y\in\sigma$ has at most one reachability interval on
every edge of $\sigma$ or $\tau$, respectively. Let
$R_{i}[j]=[\ell_{i,j},r_{i,j}]$ be the reachability interval of the vertex
$v_{i}$ on the edge $w_{j}w_{j+1}$. Let
$R^{\prime}_{j}[i]=[\ell^{\prime}_{j,i},r^{\prime}_{j,i}]$ be the reachability
interval of the vertex $w_{j}$ on the edge $v_{i}v_{i+1}$. If a reachability
interval is empty, its endpoints are taken to be null. Alt and Godau [4]
observed that $R_{i+1}[j]$ and $R^{\prime}_{j+1}[i]$ can be determined in
$O(1)$ time using $R_{i}[j]$, $R^{\prime}_{j}[i]$, and the knowledge of $\tau$
and $\sigma$. It is useful to view this computation as filling an
$(n-1)\times(m-1)$ dynamic programming table, which has one cell for every
pair of edges of $\tau$ and $\sigma$, row by row from the bottom to the top.
Consider the $(i,j)$-cell of this table. Its lower and left sides are
associated with the reachability intervals $R_{i}[j]$ and $R^{\prime}_{j}[i]$,
respectively. The dynamic programming process computes $R_{i+1}[j]$ and
$R^{\prime}_{j+1}[i]$ which are associated with the upper and right sides of
the cell, respectively. The algorithm takes $O(mn)$ time to obtain
$R_{n}[m-1]$. We have $d_{F}(\tau,\sigma)\leq\delta$ if and only if $w_{m}\in
R_{n}[m-1]$. We sketch the filling of the dynamic programming table below.

Let $\mathcal{B}_{x}$ denote the ball centered at $x$ of radius $\delta$. Let
$s_{i,j}$ and $e_{i,j}$ be the start and end of the oriented segment
$\mathcal{B}_{v_{i}}\cap w_{j}w_{j+1}$, respectively. Let $s^{\prime}_{j,i}$
and $e^{\prime}_{j,i}$ be the start and end of the oriented segment
$\mathcal{B}_{w_{j}}\cap v_{i}v_{i+1}$, respectively.

We first initialize the $R_{1}[j]$’s. If $s_{1,1}=w_{1}$, set
$\ell_{1,1}=s_{1,1}$ and $r_{1,1}=e_{1,1}$; otherwise, both $\ell_{1,1}$ and
$r_{1,1}$ are null. For all $j\in[2,m-1]$, if $r_{1,j-1}=s_{1,j}=w_{j}$, set
$\ell_{1,j}=s_{1,j}$ and $r_{1,j}=e_{i,j}$; otherwise, set $\ell_{1,j}$ and
$r_{1,j}$ to be null. The $R^{\prime}_{1}[i]$’s are similarly initialized.

Inductively, suppose that we have computed $R_{i}[j]$ and $R^{\prime}_{j}[i]$,
and we want to compute $R_{i+1}[j]$ and $R^{\prime}_{j+1}[i]$. For any point
$y\in w_{j}w_{j+1}$, a matching between $\tau[v_{1},v_{i+1}]$ and
$\sigma[w_{1},y]$ either matches $v_{i}$ to some point in $w_{j}w_{j+1}$ or
matches $w_{j}$ to some point in $v_{i}v_{i+1}$. Similarly, for any point
$x\in v_{i}v_{i+1}$, a matching between $\tau[v_{1},x]$ and
$\sigma[w_{1},w_{j+1}]$ either matches $w_{j}$ to some point in $v_{i}v_{i+1}$
or matches $v_{i}$ to some point in $w_{j}w_{j+1}$. Hence, if $R_{i}[j]$ and
$R^{\prime}_{j}[i]$ are empty, then $R_{i+1}[j]$ and $R^{\prime}_{j+1}[i]$ are
empty.

Suppose that $R^{\prime}_{j}[i]\not=\emptyset$. There exists a point $x\in
v_{i}v_{i+1}$ such that $d_{F}(\tau[v_{1},x],\sigma[w_{1},w_{j}])\leq\delta$.
So $d(x,w_{j})\leq\delta$. For every point $y\in\mathcal{B}_{v_{i+1}}\cap
w_{j}w_{j+1}$, we generate a matching between $\tau[v_{1},v_{i+1}]$ and
$\sigma[w_{1},y]$ that consists of a Fréchet matching between $\tau[v_{1},x]$
and $\sigma[w_{1},w_{j}]$ and a linear interpolation between $xv_{i+1}$ and
$w_{j}y$. This matching realizes a distance at most $\delta$, so
$d_{F}(\tau[v_{1},v_{i+1}],\sigma[w_{1},y])\leq\delta$. In other words,
$R_{i+1}[j]=\mathcal{B}_{v_{i+1}}\cap w_{j}w_{j+1}$, i.e.,
$\ell_{i+1,j}=s_{i+1,j}$ and $r_{i+1,j}=e_{i+1,j}$.

Suppose that $R^{\prime}_{j}[i]=\emptyset$ and $R_{i}[j]\not=\emptyset$. In
this case, there exists a point $y\in w_{j}w_{j+1}$ such that
$d_{F}(\tau[v_{1},v_{i}],\sigma[w_{1},y])\leq\delta$. So
$d(v_{i},y)\leq\delta$. Since $R^{\prime}_{j}[i]=\emptyset$, the vertex
$w_{j}$ cannot be matched to any point in $v_{i}v_{i+1}$. It implies that a
Fréchet matching between $\tau[v_{1},v_{i+1}]$ and $\sigma[w_{1},y]$ matches
both $v_{i}$ and $v_{i+1}$ to points in $w_{j}w_{j+1}$. Thus, the start
$\ell_{i+1,j}$ of $R_{i+1}[j]$ is the first point in the oriented segment
$s_{i+1,j}e_{i+1,j}=\mathcal{B}_{v_{i+1}}\cap w_{j}w_{j+1}$ that does not lie
in front of $\ell_{i,j}$. If such a point does not exist, then
$\ell_{i+1,j}=\text{null}$. The end $r_{i+1,j}$ of $R_{i+1}[j]$ is $e_{i+1,j}$
if $\ell_{i+1,j}\not=\text{null}$; otherwise, $r_{i+1,j}$ is null.

We can compute $R^{\prime}_{j+1}[i]$ in a similar way. The next result follows
from the discussion above.

######  Lemma 1.

If $R_{i}[j]\not=\emptyset$, then $r_{i,j}=e_{i,j}$ and
$\ell_{i,j}\in\\{\ell_{i^{\prime},j},s_{i^{\prime}+1,j},s_{i^{\prime}+2,j},\ldots,s_{i,j}\\}$
for all $i^{\prime}\in[i-1]$. Similarly, if $R^{\prime}_{j}[i]\not=\emptyset$,
then $r^{\prime}_{j,i}=e^{\prime}_{j,i}$ and
$\ell^{\prime}_{j,i}\in\\{\ell^{\prime}_{j^{\prime},i},s^{\prime}_{j^{\prime}+1,i},s^{\prime}_{j^{\prime}+2,i},\ldots,s^{\prime}_{j,i}\\}$
for all $j^{\prime}\in[j-1]$.

###  2.2 Algebraic geometry

Given a set $\mathcal{P}=\\{\rho_{1},...,\rho_{s}\\}$ of polynomials in
$\omega$ real variables, a _sign condition vector_ $S$ for $\mathcal{P}$ is a
vector in $\\{-1,0,+1\\}^{s}$. The point $\nu\in\mathbb{R}^{\omega}$
_realizes_ $S$ if
$(\text{sign}(\rho_{1}(\nu)),...,\text{sign}(\rho_{s}(\nu)))=S$. The
_realization_ of $S$ is the subset $\\{\nu\in\mathbb{R}^{\omega}:\nu\text{
realizes }S\\}$. For every $i\in[s]$, $\rho_{i}(\nu)=0$ describes a
hypersurface in $\mathbb{R}^{\omega}$. The hypersurfaces
$\\{\rho_{i}(\nu)=0:i\in[s]\\}$ partition $\mathbb{R}^{\omega}$ into open
cells of dimensions from 0 to $\omega$. This set of cells together with the
incidence relations among them form an _arrangement_ that we denote by
$\mathscr{A}(\mathcal{P})$. Each cell is a connected component of the
realization of a sign condition vector for $\mathcal{P}$; the cells in
$\mathscr{A}(\mathcal{P})$ represent all realizable sign condition vectors.

######  Theorem 1 ([7, 32]).

Given a set $\mathcal{P}$ of $s$ polynomials of constant degrees in $\omega$
variables, there are $s^{\omega}\cdot O(1)^{\omega}$ cells in
$\mathscr{A}(\mathcal{P})$. One can compute in $s^{\omega+1}\cdot
O(1)^{O(\omega)}$ time a set $Q$ of points and the sign condition vectors at
these points such that $Q$ contains at least one point in each cell of
$\mathscr{A}(\mathcal{P})$.

We will need a data structure for $\mathscr{A}(\mathcal{P})$ so that for any
query point $\nu\in\mathbb{R}^{\omega}$, we can determine implicitly the sign
condition vector at $\nu$. An easy way is to linearize the zero sets of the
polynomials in $\mathcal{P}$ to equations of hyperplanes in higher dimensions
and then use a point location data structure for an arrangement of
hyperplanes. Let $x_{1},\ldots,x_{\omega}$ denote the variables in
$\mathcal{P}$, and let $D$ denote the maximum degree. Let
$\Phi=\\{(e_{1},\ldots,e_{\omega}):\forall\,i\in[\omega],\;e_{i}\in\mathbb{Z}\,\wedge\,\sum_{i\in[\omega]}e_{i}\leq
D\\}$. A polynomial in $\mathcal{P}$ is
$\sum_{(e_{1},\ldots,e_{\omega})\in\Phi}c(e_{1},\ldots,e_{\omega})\cdot\prod_{i\in[\omega]}x_{i}^{e_{1}}$
for some coefficient $c(e_{1},\ldots,e_{\omega})$. Linearizing it means
introducing a new variable $y(e_{1},\ldots,e_{\omega})$ for each
$(e_{1},\ldots,e_{\omega})\in\Phi$ and rewriting the polynomial as
$\sum_{(e_{1},\ldots,e_{\omega})\in\Phi}c(e_{1},\ldots,e_{\omega})\cdot
y(e_{1},\ldots,e_{\omega})$. Let $M$ be the maximum number of variables in a
polynomial in $\mathcal{P}$. There are $O(\omega^{M})$ subsets of
$\\{x_{1},\ldots,x_{\omega}\\}$ that have size $M$ or less. There are less
than $(D+1)^{M}$ ways to assign exponents to the variables in each subset.
Therefore, the number of new variables is less than
$O(\omega^{M})\cdot(D+1)^{M}=O(\omega^{O(1)})$ if both $D$ and $M$ are
constants.

######  Lemma 2.

Let $\mathcal{P}$ be a set of polynomials of constant degrees and sizes in
$\omega$ variables. The zero set of each polynomial in $\mathcal{P}$ can be
linearized to a hyperplane equation that has constant size. The resulting
hyerplanes reside in $O(\omega^{O(1)})$ dimensions.

We use the point location data strucutre by Erza et al. [24]. Its query time
has a big-O constant that is independent of the dimension.

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

Let $\mathcal{H}$ be a set of $s$ hyperplanes in $\mathbb{R}^{\omega}$. For
any $\varepsilon>0$, one can construct a data structure of
$O(s^{2\omega\log\omega+O(\omega)})$ size in $O(s^{\omega+\varepsilon})$
expected time such that any query point can be located in
$\mathscr{A}(\mathcal{H})$ in $O(\omega^{3}\log s)$ time.

##  3 Overview of the decision procedure

Let $\alpha=O(\log m/\log\log m)$ be an integer. Divide $[n]$ into
$(n-1)/\alpha$ _blocks_ $B_{k}=[a_{k},a_{k+1}]$ for $k\in[(n-1)/\alpha]$,
where $a_{k}=(k-1)\alpha+1$. For example, $B_{1}=(1,\ldots,\alpha+1)$ and
$B_{2}=(\alpha+1,\ldots,2\alpha+1)$. Note that $B_{k-1}\cap
B_{k}=\\{a_{k}\\}$. $B_{k}$ represents the $\alpha$ edges
$v_{a_{k}}v_{a_{k}+1},v_{a_{k}+1}v_{a_{k}+2},\ldots,v_{a_{k+1}-1}v_{a_{k+1}}$.

We divide $[m]$ into blocks in a different way. Let $\theta=\alpha^{\mu}$ for
a constant $\mu\in(0,1)$ that will be specified later. Divide $[m]$ into
$(m-1)/\theta$ blocks $B^{\prime}_{l}=[b_{l},b_{l+1}]$ for
$l\in[(m-1)/\theta]$, where $b_{l}=(l-1)\theta+1$. $B^{\prime}_{l}$ represents
the $\theta$ edges $w_{b_{l}}w_{b_{l}+1},\ldots,w_{b_{l+1}-1}w_{b_{l+1}}$.

Split the $(n-1)\times(m-1)$ dynamic programming table into
$\alpha\times\theta$ boxes that are specified as $(B_{k},B^{\prime}_{l})$ for
some $k\in[(n-1)/\alpha]$ and $l\in[(m-1)/\theta]$. We extend the definitions
of $R_{i}[j]$ and $R^{\prime}_{j}[i]$ as follows. Let $R_{i}[j,j^{\prime}]$ be
the set of reachability intervals of $v_{i}$ on the edges
$w_{j}w_{j+1},\ldots,w_{j^{\prime}}w_{j^{\prime}+1}$. Let
$R^{\prime}_{j}[i,i^{\prime}]$ be the set of reachability intervals of $w_{j}$
on the edges $v_{i}v_{i+1},\ldots,v_{i^{\prime}}v_{i^{\prime}+1}$.

We use two encoding schemes. The first is the _signature_ of a box
$(B_{k},B^{\prime}_{l})$ which encodes some useful information about
$\tau[v_{a_{k}},v_{a_{k+1}}]$ and $\sigma[w_{b_{l}},w_{b_{l+1}}]$. A box
signature contains $\alpha+\theta$ integers, and we will show that all box
signatures can be stored in a table of size $o(mn)$. We can thus refer to a
box signature by its index. The second encoding is an encoding of reachability
intervals. The encodings of $R_{a_{k}}[b_{l},b_{l+1}-1]$ and
$R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1]$ constitute the _input encoding_ of the
box $(B_{k},B^{\prime}_{l})$. The encodings of $R_{a_{k+1}}[b_{l},b_{l+1}-1]$
and $R^{\prime}_{b_{l+1}}[a_{k},a_{k+1}-1]$ constitute the _output encoding_
of the box $(B_{k},B^{\prime}_{l})$. We will show that each input or output
encoding can be stored as one integer.

We will show how to construct the output encoding based on the input encoding
and the box signature only. Therefore, the idea is to construct a table in
preprocessing so that we can look up the output encoding of a box using a key
formed by the index of its signature and its input encoding. The reachability
information can thus be propagated in $O(1)$ time to the next box. For this
approach to work, we need to show that the number of distinct combinations of
signatures and input encodings of boxes is subquadratic. We will prove such a
bound using polynomials of constant degrees in $\theta$ variables. We also
need fast point location data structures for arrangements of hyperplanes to
efficiently retrieve the signature and input encoding of a given box.

Unfortunately, the above approach is still not fast enough. There are two
bottlenecks. First, we need to spend $\Omega(\alpha)$ time to unpack the
output encoding of one box and produce the input encoding of the next box.
Second, we need to spend $\Omega(\alpha)$ time to associate each box with its
signature. There are $\Theta(mn/(\alpha\theta))$ boxes, which makes the
decision algorithm run in $\Omega(mn/\theta)$ time. The time to compute
$d_{F}$ is thus $\Omega(mn\log(mn)/\theta)=\Omega(mn)$. To tackle these
bottlenecks, we introduce a second level of batch processing of clusters of
boxes. The idea is to retrieve the signatures of all boxes in a cluster as a
batch so that the average time per box is smaller. Similarly, we can save the
time for unpacking the output encodings and producing input encodings of boxes
that lie within a cluster.

##  4 Encoding schemes

For the rest of the paper, we will assume that $m=\Omega(n^{\varepsilon})$ for
some fixed $\varepsilon\in(0,1]$ whenever we say that some computation takes
$o(mn)$ time.

###  4.1 Box signature

Consider the box $(B_{k},B^{\prime}_{l})$. Its signature consists of the
signatures of its rows and columns. Take the column $j$ of the dynamic
programming table for some $j\in[b_{l},b_{l+1}-1]$. Let $\mathcal{I}_{j}$ be
the sequence of points
$(s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+1},j},e_{a_{k+1},j})$. As discussed
in Section 2.1, the sorted order of $\mathcal{I}_{j}$ from $w_{j}$ to
$w_{j+1}$ along $w_{j}w_{j+1}$ helps deciding $R_{i+1}[j]$ from $R_{i}[j]$.
The signature of column $j$ is an array $\phi$ of size $2(a_{k+1}-a_{k}+1)$.
For every $i\in B_{k}$, $\phi[2i-2a_{k}+1]$ and $\phi[2i-2a_{k}+2]$ store the
ranks of $s_{i,j}$ and $e_{i,j}$, respectively, when $\mathcal{I}_{j}$ is
ordered from $w_{j}$ to $w_{j+1}$ along $w_{j}w_{j+1}$. If $s_{i,j}$ and
$e_{i,j}$ are null, $\phi[2i-2a_{k}+1]$ and $\phi[2i-2a_{k}+2]$ are equal to
$2\alpha+3$. An example is given in Figure 1. The signature of row $i$ for
some $i\in[a_{k},a_{k+1}-1]$ is defined analogously by sorting the
$\mathcal{I}^{\prime}_{i}=(s^{\prime}_{b_{l},i},e^{\prime}_{b_{l},i},\ldots,s^{\prime}_{b_{l+1},i},e^{\prime}_{b_{l+1},i})$
along the edge $v_{i}v_{i+1}$. The signature of a row or column requires
$O(\alpha\log\alpha)=O(\log m)$ bits, so it can be stored as an integer. The
box signature consists of the signatures of $\alpha$ rows and $\theta$
columns.

Computing a box signature as described above requires
$O(\alpha\theta\log\alpha)$ time. We cannot afford it during dynamic
programming as there are $O(mn/(\alpha\theta))$ boxes. Also, as the box
signature consists of $\alpha+\theta$ integers, we will not be able to combine
it with the input encoding of a box to form a key that can be stored in a
word. This is contrary to the high-level approach sketched in Section 3.
Fortunately, we will show in Section 5 that there are $o(mn)$ distinct box
signatures. So we can store them in a table of $o(mn)$ size and represent a
box signature by its table index. We will construct a two-dimensional array
whose $(k,l)$-entry stores the index of the signature of the box
$(B_{k},B^{\prime}_{l})$.

Figure 1: Suppose that $B_{k}=[1,5]$ and all balls in this figure have radius
$\delta$. The signature of column $j$ is $\phi=(1,2,3,4,5,7,6,8,11,11)$.

###  4.2 Encoding of reachability intervals

The reachability interval $R_{i}[j]$ is encoded with respect to a block
$B_{k}$ that contains $i$. We denote the encoding by
$\mathrm{code}_{B_{k}}(R_{i}[j])$. Note that $R_{a_{k+1}}[j]$ may have
different encodings $\mathrm{code}_{B_{k}}(R_{a_{k+1}}[j])$ and
$\mathrm{code}_{B_{k+1}}(R_{a_{k+1}}[j])$ with respect to $B_{k}$ and
$B_{k+1}$, respectively. Similarly, $R^{\prime}_{j}[i]$ is encoded with
respect to a block $B^{\prime}_{l}$ that contains $j$, and we denote the
encoding by $\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{j}[i])$.

We use $\mathrm{code}_{B_{k}}(R_{i}[b_{l},b_{l+1}-1])$ to denote
$\mathrm{code}_{B_{k}}(R_{i}[j])$ for all $j\in[b_{l},b_{l+1}-1]$. The
shorthand $\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{j}[a_{k},a_{k+1}-1])$ is
defined analogously. The _input encoding_ of the box $(B_{k},B^{\prime}_{l})$
consists of $\mathrm{code}_{B_{k}}(R_{a_{k}}[b_{l},b_{l+1}-1])$ and
$\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1])$. The
_output encoding_ of the box $(B_{k},B^{\prime}_{l})$ consists of
$\mathrm{code}_{B_{k}}(R_{a_{k+1}}[b_{l},b_{l+1}-1])$ and
$\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{b_{l+1}}[a_{k},a_{k+1}-1])$.

Consider a block $B_{k}$ and some $i\in B_{k}$. As discussed in Section 2.1,
if $R_{i}[j]=\emptyset$, both $\ell_{i,j}$ and $r_{i,j}$ are null; otherwise,
$r_{i,j}=e_{i,j}$. Therefore, it suffices to encode $\ell_{i,j}$, which
belongs to $(\ell_{a_{k},j},s_{a_{k},j},s_{a_{k}+1,j},\ldots,s_{a_{k+1},j})$
by Lemma 1. We define $\mathrm{code}_{B_{k}}(R_{i}[j])$ to be a 3-tuple
$(\pi_{i,j},\beta_{i,j},\gamma_{i,j})\in[2\alpha+3]\times\\{0,1\\}\times[0,\alpha+1]$
with the following meaning.

If $R_{i}[j]=\emptyset$, then $\pi_{i,j}=2\alpha+3$, signifying that
$\ell_{i,j}$ is null; the values of $\beta_{i,j}$ and $\gamma_{i,j}$ are
irrelevant in this case. Suppose that $R_{i}[j]\not=\emptyset$. Then,
$\gamma_{i,j}$ tells us which element in
$(\ell_{a_{k},j},s_{a_{k},j},\ldots,s_{a_{k+1},j})$ is $\ell_{i,j}$. We need
not store the sequence $(\ell_{a_{k},j},s_{a_{k},j},\ldots,s_{a_{k+1},j})$
explicitly. If $\gamma_{i,j}\in[\alpha+1]$, then
$\ell_{i,j}=s_{a_{k}+\gamma_{i,j}-1,j}$. If $\gamma_{i,j}=0$, then
$\ell_{i,j}=\ell_{a_{k},j}$, and the $\pi_{i,j}$-th element in the sorted
order of $\\{s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+1},j},e_{a_{k+1},j}\\}$
along $w_{j}w_{j+1}$ is the immediate predecessor of $\ell_{a_{k},j}$. Also,
$\beta_{i,j}=1$ if and only if $\ell_{a_{k},j}$ is equal to this immediate
predecessor.

The encoding $\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{j}[i])$ is defined
analogously as a 3-tuple
$(\pi^{\prime}_{j,i},\beta^{\prime}_{j,i},\gamma^{\prime}_{j,i})$. The input
or output encoding of a box uses $O(\alpha\log\alpha)=O(\log m)$ bits, so it
can be stored as an integer.

Suppose that $i+1\in B_{k}$. We describe how to produce
$\mathrm{code}_{B_{k}}(R_{i+1}[j])$ using the signature of
$(B_{k},B^{\prime}_{l})$, $\mathrm{code}_{B_{k}}(R_{i}[j])$, and
$\mathrm{code}_{B^{\prime}_{l}}(R_{j}[i])$. As described in Section 2.1, we
need to decide whether $R_{i}[j]$ or $R^{\prime}_{j}[i]$ is null, which can be
done by checking whether $\pi_{i,j}$ or $\pi^{\prime}_{j,i}$ is equal to
$2\alpha+3$. Next, we need to compare $\ell_{i,j}$ with $s_{i+1,j}$ and
$e_{i+1,j}$. There are two cases in handling this comparison.

Suppose that $\gamma_{i,j}\in[\alpha+1]$. We have
$\ell_{i,j}=s_{a_{k}+\gamma_{i,j}-1,j}$ in this case. We use the signature
$\phi$ of column $j$ to retrieve $\phi[2\gamma_{i,j}-1]$, which is the rank of
$s_{a_{k}+\gamma_{i,j}-1,j}$ among the points in $\mathcal{I}_{j}$ ordered
from $w_{j}$ to $w_{j+1}$ along $w_{j}w_{j+1}$. Comparing
$\phi[2\gamma_{i,j}-1]$ with $\phi[2(i+1)-2a_{k}+1]$ and
$\phi[2(i+1)-2a_{k}+2]$ give the results of comparing $\ell_{i,j}$ with
$s_{i+1,j}$ and $e_{i+1,j}$, which allow us to determine $\ell_{i+1,j}$ as
described in Section 2.1. If $\ell_{i+1,j}$ is not null, it is equal to either
$s_{a_{k}+\gamma_{i,j}-1,j}$ or $s_{i+1,j}$. We thus construct
$\mathrm{code}_{B_{k}}(R_{i+1}[j])$ as follows. If $\ell_{i+1,j}$ is null, set
$\pi_{i+1,j}=2\alpha+3$; if $\ell_{i+1,j}=s_{a_{k}+\gamma_{i,j}-1,j}$, set
$\gamma_{i+1,j}=\gamma_{i,j}$; if $\ell_{i+1,j}=s_{i+1,j}$, set
$\gamma_{i+1,j}=i-a_{k}+2$.

Suppose that $\gamma_{i,j}=0$. So $\ell_{i,j}=\ell_{a_{k},j}$. Given the
signature $\phi$ of column $j$, we get the rank $\phi[\pi_{i,j}]$ of the
immediate predecessor of $\ell_{i,j}$ among the points in $\mathcal{I}_{j}$
sorted along $w_{j}w_{j+1}$. We use $\beta_{i,j}$ and the comparsions of
$\phi[\pi_{i,j}]$ with $\phi[2(i+1)-2a_{k}+1]$ and $\phi[2(i+1)-2a_{k}+2]$ to
determine the comparsions of $\ell_{a_{k},j}$ with $s_{i+1,j}$ and
$e_{i+1,j}$. This tells us whether $\ell_{i+1,j}$ is null, $\ell_{a_{k},j}$,
or $s_{i+1,j}$ as described in Section 2.1. We construct
$\mathrm{code}_{B_{k}}(R_{i+1}[j])$ as follows. If $\ell_{i+1,j}$ is null, set
$\pi_{i+1,j}=2\alpha+3$; if $\ell_{i+1,j}=\ell_{a_{k},j}$, set
$\gamma_{i+1,j}=0$, $\pi_{i+1,j}=\pi_{i,j}$, and $\beta_{i+1,j}=\beta_{i,j}$;
if $\ell_{i+1,j}=s_{i+1,j}$, set $\gamma_{i+1,j}=i-a_{k}+2$.

Hence, we can compute $\mathrm{code}_{B_{k}}(R_{i+1}[j])$ in $O(1)$ time.
Similarly, if $j+1\in B^{\prime}_{l}$, we can also compute
$\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{j+1}[i])$ in $O(1)$ time. In all,
given the signature of the box $(B_{k},B^{\prime}_{l})$ and its input
encoding, we can process the cells in the box row by row to obtain the output
encoding.

######  Lemma 3.

Given the signature of a box $(B_{k},B^{\prime}_{l})$ and its input encoding,
we can compute its output encoding in $O(\alpha\theta)$ time. The signature
consists of $\alpha+\theta$ integers. The input encoding occupies one integer,
and so does the output encoding.

##  5 Subquadratic decision algorithm

###  5.1 Preprocessing

Given an oriented line segment $pq$, we say $x\leq_{pq}y$ for two points
$x,y\in pq$ if $x$ is not behind $y$ along $pq$. Consider a box
$(B_{k},B^{\prime}_{l})$ and the predicates in Table 1 over all
$i,i^{\prime}\in B_{k}$ and $j,j^{\prime}\in B^{\prime}_{l}$. $P_{1}$ and
$P_{2}$ capture the distances between the vertices of $\tau$ and the edges of
$\sigma$ and vice versa. For each $j$, $P_{4}$, $P_{6}$, and $P_{8}$ capture
the ordering of the endpoints of $\mathcal{B}_{v_{i}}\cap w_{j}w_{j+1}$ for
$i\in B_{k}$ along the edge $w_{j}w_{j+1}$. For each $i$, $P_{3}$, $P_{5}$,
and $P_{7}$ capture the ordering of the endpoints of $\mathcal{B}_{w_{j}}\cap
v_{i}v_{i+1}$ for $j\in B^{\prime}_{l}$ along the edge $v_{i}v_{i+1}$. Hence,
we can determine the signatures of all rows and columns of the box
$(B_{k},B^{\prime}_{l})$ from the truth values of these predicates without
checking $\tau$ and $\sigma$ further.

$P_{1}(i,j)=\text{true}$ $\iff$ $d(w_{j},v_{i}v_{i+1})\leq\delta$
$P_{2}(i,j)=\text{true}$ $\iff$ $d(v_{i},w_{j}w_{j+1})\leq\delta$
$P_{3}(i,j,j^{\prime})=\text{true}$ $\iff$ $\text{neither $s^{\prime}_{j,i}$
nor $s^{\prime}_{j^{\prime},i}$ is
null}\,\wedge\,s^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}s^{\prime}_{j^{\prime},i}$
$P_{4}(i,i^{\prime},j)=\text{true}$ $\iff$ $\text{neither $s_{i,j}$ nor
$s_{i^{\prime},j}$ is
null}\,\wedge\,s_{i,j}\leq_{w_{j}w_{j+1}}s_{i^{\prime},j}$
$P_{5}(i,j,j^{\prime})=\text{true}$ $\iff$ $\text{neither $e^{\prime}_{j,i}$
nor $e^{\prime}_{j^{\prime},i}$ is
null}\,\wedge\,e^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}e^{\prime}_{j^{\prime},i}$
$P_{6}(i,i^{\prime},j)=\text{true}$ $\iff$ $\text{neither $e_{i,j}$ nor
$e_{i^{\prime},j}$ is
null}\,\wedge\,e_{i,j}\leq_{w_{j}w_{j+1}}e_{i^{\prime},j}$
$P_{7}(i,j,j^{\prime})=\text{true}$ $\iff$ $\text{neither $s^{\prime}_{j,i}$
nor $e^{\prime}_{j^{\prime},i}$ is
null}\,\wedge\,s^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}e^{\prime}_{j^{\prime},i}$
$P_{8}(i,i^{\prime},j)=\text{true}$ $\iff$ $\text{neither $s_{i,j}$ nor
$e_{i^{\prime},j}$ is
null}\,\wedge\,s_{i,j}\leq_{w_{j}w_{j+1}}e_{i^{\prime},j}$

Table 1: There are $O(\alpha^{3})$ predicates over all $i,i^{\prime}\in B_{k}$
and $j,j^{\prime}\in B^{\prime}_{l}$.

####  5.1.1 Signature data structures

Fix $B_{k}$. Consider a sequence $(w_{\ell},\ldots,w_{\ell+\theta})$. The
signatures of rows and columns of the box specified by $B_{k}$ and
$[\ell,\ell+\theta]$ are completely determined by the truth values of
$P_{1},\ldots,P_{8}$ over all $i,i^{\prime}\in B_{k}$ and
$j,j\in[\ell,\ell+\theta]$. By treating $\delta$ and the coordinates of
$v_{a_{k}},\ldots,v_{a_{k+1}}$ as coefficients and the coordinates of
$w_{\ell},\ldots,w_{\ell+\theta}$ as $d(\theta+1)$ variables, we can formulate
a set $\mathcal{P}_{k}$ of $O(\alpha^{2}\theta)$ polynomials of constant
degrees and sizes in these $d(\theta+1)$ variables that implement
$P_{1},\ldots,P_{8}$ over all $i,i^{\prime}\in B_{k}$ and $j,j^{\prime}\in
B^{\prime}_{l}$. Each sign condition vector for $\mathcal{P}_{k}$ determines
the signature of a box that involves $B_{k}$. These polynomials are specified
in Appendix A. By Theorem 1, there are at most $\alpha^{O(\theta)}$ sign
condition vectors of $\mathcal{P}_{k}$, and we can compute them all in
$\alpha^{O(\theta)}$ time.222It is customary to write $O(\alpha^{O(\theta)})$.
To simplify the exposition, when we have a term $t^{O(h)}$ inside the big-Oh
such that $t$ is an increasing function in $m$ or $n$ and $h\geq 1$, we can
increase the hidden constant in the exponent $O(h)$ to absorb the big-Oh
constant. We will do without the big-Oh this way. We assign unique indices
from the range $[\alpha^{O(\theta)}]$ to these sign condition vectors. For
each sign condition vector $\nu$, we compute the corresponding box signature
and store it in the array entry Signa$[k,\mathit{id}]$, where $\mathit{id}$ is
the index of $\nu$. Repeating the above for all $k\in[(n-1)/\alpha]$ produces
the array Signa in $n\alpha^{O(\theta)}$ time.

######  Lemma 4.

We can compute in $n\alpha^{O(\theta)}$ time the array
Signa$[1\,..\,(n-1)/\alpha,1\,..\,\alpha^{O(\theta)}]$. For every
$k\in[(n-1)/\alpha]$, the subarray Signa$[k]$ stores the signatures of all
boxes that involve $B_{k}$.

####  5.1.2 Reachability propagation and indexing

We want to construct a table Map so that for any index _key_ that gives the
signature of a box and its input encoding, Map can be accessed in $O(1)$ time
to return the output encoding for _key_. The box signatures can be obtained by
going through Signa. Since the encoding of a reachability interval is an
element of $[2\alpha+3]\times\\{0,1\\}\times[0,\alpha+1]$, there are
$O(\alpha^{2})$ possibilities. There $\alpha+\theta$ reachability intervals,
so there are $O(\alpha^{2})^{\alpha+\theta}=\alpha^{O(\alpha)}$ possibilities
which can be enumerated in $\alpha^{O(\alpha)}$ time. An index of Map consists
of $k\in[(n-1)/\alpha]$ and $\mathit{id}\in[\alpha^{O(\theta)}]$ that specify
a box signature in Signa as well as $O(\alpha\log\alpha)$ bits that represent
an input encoding. Such an index can be stored in $\log n+O(\alpha\log\alpha)$
bits which can fit into one word. As a result, Map can be accessed in $O(1)$
time. Every entry of Map can be computed in $O(\alpha\theta)$ time by Lemma 3.

######  Lemma 5.

We can compute Map in $n\alpha^{O(\alpha)}$ time and space.

We want to construct an array Index$[1\,..\,(n-1)/\alpha,1\,..\,(m-1)/\theta]$
so that Signa$[k,\text{\sc Index}[k,l]]$ stores the signature of the box
$(B_{k},B^{\prime}_{l})$. We linearize the zero sets of the polynomials in
$\mathcal{P}_{k}$ to a set $\mathcal{H}_{k}$ of hyperplanes. There are
$d(\theta+1)$ variables in $\mathcal{P}_{k}$. By Lemma 2, the linearization
gives rise to $O(\theta^{L})$ variables for some constant $L>1$. By Theorem 1,
we can construct a point location data structure for
$\mathscr{A}(\mathcal{H}_{k})$ such that a query can be answered in
$O(\theta^{3L}\log\alpha)$ time. For each $l\in[(m-1)/\theta]$, we use the
coordinates of $w_{b_{l}},\ldots,w_{b_{l+1}}$ to compute the values of the
variables for $\mathcal{H}_{k}$ and then query the point location data
structure in $O(\theta^{3L}\log\alpha)$ time. This gives the index
$\mathit{id}$ for the sign condition vector of $\mathcal{P}_{k}$ induced by
$(B_{k},B^{\prime}_{l})$. We set Index$[k,l]=\mathit{id}$. The above
construction takes $\alpha^{O(\theta^{L}\log\theta)}$ expected time and
$\alpha^{O(\theta^{L})}$ space by Theorem 1. Recall that
$\theta=\alpha^{\mu}$. We choose a constant $\mu<1/L$ so that
$\theta^{L}\log\theta<\alpha$. If $\alpha=c\log m/\log\log m$ for a small
enough constant $c$, the time to construct the point location data structures
is $n\alpha^{O(\theta^{L}\log\theta)}=n\alpha^{O(\alpha)}=O(nm^{\varepsilon})$
for some $\varepsilon\in(0,1)$, which is dominated by the point location cost
for the entries of Index.

######  Lemma 6.

If $\theta^{L}\log\theta<\alpha$, we can construct Index in
$O(mn\theta^{3L-1}\log\alpha/\alpha)$ expected time and $O(mn/(\alpha\theta))$
space.

####  5.1.3 $\boldsymbol{B_{k}}$-coder and $\boldsymbol{B^{\prime}_{l}}$-coder

When we reach the box $(B_{k},B^{\prime}_{l})$ during dynamic programming, we
have read $\mathrm{code}_{B_{k-1}}(R_{a_{k}}[b_{l},b_{l+1}-1])$ and
$\mathrm{code}_{B^{\prime}_{l-1}}(R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1])$ from
Map. To read the output encoding of the box $(B_{k},B^{\prime}_{l})$ from Map,
we must first produce its input encoding
$\mathrm{code}_{B_{k}}(R_{a_{k}}[b_{l},b_{l+1}-1])$ and
$\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1])$. The
$B_{k}$-coder and $B^{\prime}_{l}$-coder serve this purpose.

It is easy to unpack $\mathrm{code}_{B_{k-1}}(R_{a_{k}}[b_{l},b_{l+1}-1])$ and
$\mathrm{code}_{B^{\prime}_{l-1}}(R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1])$ to
$R_{a_{k}}[b_{l},b_{l+1}-1]$ and $R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1]$ in
$O(\alpha\log\alpha)$ time, respectively. This gives us the coordinates of
$\ell_{a_{k},j}$ and $r_{a_{k},j}$ for $j\in[b_{l},b_{l+1}-1]$ and those of
$\ell^{\prime}_{b_{l},i}$ and $r^{\prime}_{b_{l},i}$ for
$i\in[a_{k},a_{k+1}-1]$. We describe the $B_{k}$-coder. The
$B^{\prime}_{l}$-coder is built similarly. Given any $R_{a_{k}}[j]$, the
$B_{k}$-coder is to return a 3-tuple
$(\pi_{a_{k},j},\beta_{a_{k},j},\gamma_{a_{k},j})$ as
$\mathrm{code}_{B_{k}}(R_{a_{k}}[j])$. Let
$(\pi_{a_{k-1},j},\beta_{a_{k-1},j},\gamma_{a_{k-1},j})$ be
$\mathrm{code}_{B_{k-1}}(R_{a_{k}}[j])$.

If $R_{a_{k}}[j]=\text{null}$, set $\pi_{a_{k},j}=2\alpha+3$ and we are done.
Suppose not. If $\gamma_{a_{k-1},j}\in[\alpha+1]$, then
$\ell_{a_{k},j}=s_{a_{k-1}+\gamma_{a_{k-1},j}-1,j}$. If
$\gamma_{a_{k-1},j}=0$, then $\ell_{a_{k},j}=\ell_{a_{k-1},j}$. We have
inductively computed the coordinates of $\ell_{a_{k-1},j}$. As a result, we
know the coordinates of $\ell_{a_{k},j}$ in both cases, and it suffices to
locate $\ell_{a_{k},j}$ among the sorted order of
$s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+1},j},e_{a_{k+1},j}$ along
$w_{j}w_{j+1}$ to determine
$(\pi_{a_{k},j},\beta_{a_{k},j},\gamma_{a_{k},j})$. We cannot afford to
maintain the sorted sequence for all choices of $w_{j}w_{j+1}$ explicitly.
Instead, we formulate $O(\alpha)$ polynomials of constant degrees in $3d$
variables to model the positioning of an unknown point among the sorted order
of $s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+1},j},e_{a_{k+1},j}$ along
$w_{j}w_{j+1}$. The $3d$ variables correspond to the coordinates of the
unknown point, $w_{j}$, and $w_{j+1}$. These polynomials are specified in
Appendix B. We linearize the zero sets of these polynomials to hyperplanes and
construct the point location data structure in Theorem 2. During dynamic
programming, we query this data structure with
$(\ell_{a_{k},j},w_{j},w_{j+1})$ to get $\mathrm{code}_{B_{k}}(R_{a_{k}}[j])$.

######  Lemma 7.

Each $B_{k}$-coder can be built in $\alpha^{O(1)}$ space and expected time.
Given $R_{a_{k}}[b_{l},b_{l+1}-1]$, computing
$\mathrm{code}_{B_{k}}(R_{a_{k}}[b_{l},b_{l+1}-1])$ takes
$O(\theta\log\alpha)$ time. Each $B^{\prime}_{l}$-coder can be built in
$\theta^{O(1)}$ space and expected time. Given
$R^{\prime}_{b^{\prime}_{l}}[a_{k},a_{k+1}-1]$, computing
$\mathrm{code}_{B^{\prime}_{l}}(R^{\prime}_{b_{l}}[a_{k},a_{k+1}-1])$ takes
$O(\alpha\log\theta)$ time.

###  5.2 Dynamic programming

Initialize $R_{1}[1,m-1]$ and $R^{\prime}_{1}[1,n-1]$ in $O(m+n)$ time. By
Lemma 7, we query the $B_{1}$-coder and the $B^{\prime}_{1}$-coder to obtain
$\mathrm{code}_{B_{1}}(R_{1}[b_{l},b_{l+1}-1])$ for all $l\in[(m-1)/\theta]$
and $\mathrm{code}_{B^{\prime}_{1}}(R^{\prime}_{1}[a_{k},a_{k+1}-1])$ for all
$k\in[(n-1)/\alpha]$. The time needed is
$O(m\log\alpha+n\log\theta)=O(n\log\alpha)$.

We now have the input encoding of the box $(B_{1},B^{\prime}_{1})$.
Concatenate the binary representation of 1, Signa$[1,\text{\sc Index}[1,1]]$,
and this input encoding to form an index key. Map$[\mathit{key}]$ stores the
output encoding, i.e., $\mathrm{code}_{B_{1}}(R_{a_{2}}[b_{1},b_{2}-1])$ and
$\mathrm{code}_{B^{\prime}_{1}}(R^{\prime}_{b_{2}}[a_{1},a_{2}-1])$. Unpack
$\mathrm{code}_{B^{\prime}_{1}}(R^{\prime}_{b_{2}}[a_{1},a_{2}-1])$ to
$R^{\prime}_{b_{2}}[a_{1},a_{2}-1]$ in $O(\alpha\log\alpha)$ time. Use the
$B^{\prime}_{2}$-coder to compute
$\mathrm{code}_{B^{\prime}_{2}}(R^{\prime}_{b_{2}}[a_{1},a_{2}-1])$ in
$O(\alpha\log\theta)$ time. We now have the input encoding of the box
$(B_{1},B^{\prime}_{2})$. We can then repeat to process
$(B_{1},B^{\prime}_{l})$ for all $l\in[(m-1)/\theta]$. The time needed is
$O(m\alpha\log\alpha/\theta)$.

We now have $\mathrm{code}_{B_{1}}(R_{a_{2}}[b_{l},b_{l+1}-1])$ for all
$l\in[(m-1)/\theta]$. Unpack them to $R_{a_{2}}[b_{l},b_{l+1}-1]$ and use the
$B_{2}$-coder to compute $\mathrm{code}_{B_{2}}(R_{a_{2}}[b_{l},b_{l+1}-1])$
for all $l\in[(m-1)/\theta]$. This takes
$O((m/\theta)\cdot\theta\log\alpha)=O(m\log\alpha)$ time. We proceed as before
to process $(B_{2},B^{\prime}_{l})$ for all $l\in[(m-1)/\theta]$ in
$O(m\alpha\log\alpha/\theta)$ time. There are $(n-1)/\alpha$ rows, hence a
total of $O(mn\log\alpha/\theta)$ time.

######  Lemma 8.

After the proprocessing in Section 5.1, computing $R_{n}[m-1]$ takes
$O(mn\log\alpha/\theta)$ time.

##  6 Further improvement

Lemmas 4–8 imply that the decision algorithm runs in
$O(mn\theta^{3L-1}\log\alpha/\alpha+mn\log\alpha/\theta)$ expected time. In
this section, we improve it to $O(mn\log^{2}\alpha/(\alpha\theta))$ by
proposing a second level batch processing to tackle the bottlenecks in Lemmas
6 and 8.

###  6.1 Signatures

To deal with the bottleneck in Lemma 6, we cluster the boxes into
$\alpha\times 1$ disjoint tiles which we call _racks_. A rack is an
$\alpha\times 1$ array of boxes or an $\alpha^{2}\times\theta$ array of cells
of the dynamic programming table. Each rack is specified as
$(\hat{B}_{\kappa},B^{\prime}_{l})$, where $\hat{B}_{\kappa}$ consists of
$B_{k},B_{k+1},\ldots,B_{k+\alpha-1}$ for some $k$.

Consider the predicates $P_{1},\ldots,P_{8}$ over all
$i,i^{\prime}\in\hat{B}_{\kappa}$ and $j,j^{\prime}\in[\ell,\ell+\theta]$ for
some $\ell$. There are $O(\alpha^{4}\theta)$ of them, and their truth values
determine the signatures of the boxes inside the rack
$(\hat{B}_{\kappa},[\ell,\ell+\theta])$. By treating the coordinates of
$w_{\ell},\ldots,w_{\ell+\theta}$ as variables, we can formulate a set
$\mathcal{Q}_{k}$ of $O(\alpha^{4}\theta)$ polynomials of constant degrees and
sizes that implement the predicates.

By Theorem 1, we compute in $\alpha^{O(\theta)}$ time all sign condition
vectors of $\mathcal{Q}_{\kappa}$ and the box signatures associated with them.
Assign unique indices from the range $[\alpha^{O(\theta)}]$ to these sign
condition vectors. Take a sign condition vector $\nu$ of
$\mathcal{Q}_{\kappa}$. For each $i\in[\alpha]$, the vector $\nu$ induces one
box signature $\xi_{i}$ that involves $B_{k+i-1}$, and we set
Signa$[k+i-1,\mathit{id}]=\xi_{i}$, where $\mathit{id}$ is the index of $\nu$.

For each $\kappa$, we fill the subarrays Index$[k+i-1]$ for all $i\in[\alpha]$
as follows. Linearize $\mathcal{Q}_{\kappa}$ to a set $\mathcal{H}_{\kappa}$
of hyperplanes. There are $O(\theta^{L})$ variables in $\mathcal{H}_{\kappa}$
for some constant $L>1$. Construct the point location data structure for
$\mathscr{A}(\mathcal{H}_{\kappa})$ in $\alpha^{O(\theta^{L}\log\theta)}$
expected time. For each $l\in[(m-1)/\theta]$, use the coordinates of
$w_{b_{l}},\ldots,w_{b_{l+1}}$ to query this data structure in
$O(\theta^{3L}\log\alpha)$ time. It returns a sign condition vector $\nu$. Let
$\mathit{id}$ be the index of $\nu$. We set Index$[k+i-1,l]=\mathit{id}$ for
all $i\in[\alpha]$.

We spend $n\alpha^{O(\theta)}$ time to compute the sign conditions vectors of
$\mathcal{Q}_{\kappa}$ for all $\kappa$ and the array Signa. We spend
$n\alpha^{O(\theta^{L}\log\theta)}\leq n\alpha^{O(\alpha)}$ expected time to
obtain the point location data structures for
$\mathscr{A}(\mathcal{H}_{\kappa})$ for all $\kappa$. We also spend
$O(\theta^{3L}\log\alpha)$ to perform the point location for every rack; the
total over all racks is
$O(mn\theta^{3L}\log\alpha/(\alpha^{2}\theta))=O(mn\log\alpha/(\alpha\theta))$,
provided that $\theta^{3L}=\alpha^{3\mu L}<\alpha$, i.e., choose $\mu<1/(3L)$.
Note that $n\alpha^{O(\theta)}\leq n\alpha^{O(\alpha)}$ is dominated by
$O(mn\log\alpha/(\alpha\theta))$.

######  Lemma 9.

If $\theta^{3L}<\alpha$, we can compute Signa and Index in
$O(mn\log\alpha/(\alpha\theta))$ expected time.

###  6.2 Input encoding generation

The bottleneck in Lemma 8 arises from unpacking the output encoding of the box
$(B_{k},B^{\prime}_{l})$ and calling the $B_{k+1}$-coder and the
$B^{\prime}_{l+1}$-coder. We cluster the boxes into
$\alpha\times\alpha^{2}/\theta$ tiles which we call _superboxes_. A superbox
is an $\alpha\times\alpha^{2}/\theta$ array of boxes or an
$\alpha^{2}\times\alpha^{2}$ array of cells of the dynamic programming table.
So there are $\Theta(mn/\alpha^{4})$ superboxes. We specify each superbox as
$(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda})$ where $\hat{B}_{\kappa}$
consists of $B_{k},B_{k+1},\ldots,B_{k+\alpha-1}$ for some appropriate $k$,
and $\hat{B}_{\lambda}$ consists of
$B^{\prime}_{l},B^{\prime}_{l+1},\ldots,B^{\prime}_{l+\alpha^{2}/\theta-1}$
for some appropriate $l$.

Our solution is to derive the input and output encodings of all boxes within
the superbox $(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda})$ with respect to
$\hat{B}_{\kappa}$ and $\hat{B}^{\prime}_{\lambda}$. No unpacking and recoding
is needed within a superbox. We only need to perform such unpacking and
recoding when the dynamic programming process proceeds from
$(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda})$ to
$(\hat{B}_{\kappa+1},\hat{B}^{\prime}_{\lambda})$ and
$(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda+1})$.

What does it mean to encode a reachability interval $R_{i}[j]$ with respect to
$\hat{B}_{\kappa}$? The encoding is also a 3-tupe
$(\hat{\pi}_{i,j},\hat{\beta}_{i,j},\hat{\gamma}_{i,j})$ as in the case of
boxes. The difference is that $\hat{\pi}_{i,j}$ and $\hat{\gamma}_{i,j}$ come
from bigger domains. Specifically,
$(\hat{\pi}_{i,j},\hat{\beta}_{i,j},\hat{\gamma}_{i,j})\in[2(\alpha^{2}+1)+1]\times\\{0,1\\}\times[0,\alpha^{2}+1]$.
The element $\hat{\gamma}_{i,j}$ tells us which element of
$(\ell_{a_{k},j},s_{a_{k},j},\ldots,s_{a_{k+\alpha},j})$ is equal to
$\ell_{i,j}$. If $\hat{\gamma}_{i,j}\in[\alpha^{2}+1]$, then
$\ell_{i,j}=s_{a_{k}+\hat{\gamma}_{i,j}-1,j}$. If $\hat{\gamma}_{i,j}=0$, then
$\ell_{i,j}=\ell_{a_{k},j}$, and the $\hat{\pi}_{i,j}$-th element in the
sequence
$(s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+\alpha},j},e_{a_{k+\alpha},j})$ is
the immediate predecessor of $\ell_{i,j}$ in the sorted order of this sequence
along $w_{j}w_{j+1}$. Also, $\hat{\beta}_{i,j}=1$ if and only if
$\ell_{a_{\kappa},j}$ is equal to this immediate predecessor.

As a result, we can construct the $\hat{B}_{\kappa}$-coder as in the
construction of a $B_{k}$-coder in Section 5.1.3. The only difference is that
there are $O(\alpha^{2})$ polynomials instead of $O(\alpha)$ polynomials. The
construction time remains to be $\alpha^{O(1)}$. The query time remains to be
$O(\log\alpha)$.

The $\hat{B}^{\prime}_{\lambda}$-coder is also organized like the
$B^{\prime}_{l}$-coder. The difference is that the $B^{\prime}_{l}$-coder
involves $\theta$ columns and hence $O(\theta)$ polynomials, but the
$\hat{B}^{\prime}_{\lambda}$-coder involves $\alpha^{2}$ and hence
$O(\alpha^{2})$ polynomials like the $\hat{B}_{\kappa}$-coder. So the
$\hat{B}^{\prime}_{\lambda}$ has the same performance as the
$\hat{B}_{\kappa}$-coder.

######  Lemma 10.

Each $\hat{B}_{\kappa}$-coder and each $\hat{B}^{\prime}_{\lambda}$-coder can
be built in $\alpha^{O(1)}$ space and expected time. Given
$R_{a_{\kappa}}[b_{\lambda},b_{\lambda+1}-1]$, computing
$\mathrm{code}_{\hat{B}_{\kappa}}(R_{a_{\kappa}}[b_{\lambda},b_{\lambda+1}-1])$
takes $O(\alpha^{2}\log\alpha)$ time. The same result holds for computing
$\mathrm{code}_{\hat{B}^{\prime}_{\lambda}}(R^{\prime}_{b_{\lambda}}[a_{\kappa},a_{\kappa+1}-1])$
from $R^{\prime}_{b_{\lambda}}[a_{\kappa},a_{\kappa+1}-1]$.

When proceeding from $(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda})$ to
$(\hat{B}_{\kappa+1},\hat{B}^{\prime}_{\lambda})$, we unpack
$\mathrm{code}_{\hat{B}_{\kappa}}(R_{a_{\kappa+1}}[b_{\lambda}-b_{\lambda+1}-1])$
to $R_{a_{\kappa+1}}[b_{\lambda}-b_{\lambda+1}-1]$ in
$O(\alpha^{2}\log\alpha)$ time. We compute
$\mathrm{code}_{\hat{B}_{\kappa+1}}(R_{a_{\kappa}}[b_{\lambda},b_{\lambda+1}-1])$
in $O(\alpha^{2}\log\alpha)$ time by Lemma 10. The same can be said for
proceeding from $(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda})$ to
$(\hat{B}_{\kappa},\hat{B}^{\prime}_{\lambda+1})$. The total over all
$O(mn/\alpha^{4})$ superboxes is $O(mn\log\alpha/\alpha^{2})$.

######  Lemma 11.

Suppose that Signa, Index, and the $\hat{B}_{\kappa}$-coder and
$\hat{B}^{\prime}_{\lambda}$-coder are available for all
$\kappa\in[(n-1)/\alpha^{2}]$ and $\lambda\in[(m-1)/\alpha^{2}]$. We can
compute $R_{n}[m-1]$ in $O(mn\log\alpha/\alpha^{2})$ time.

Putting Lemmas 5, 9, 10, and 11 together gives our main results. Recall that
$\theta=\alpha^{\mu}$ and $\alpha=O(\log m/\log\log m)$.

######  Theorem 3.

Let $\sigma$ and $\tau$ be two polygonal curves of sizes $m$ and $n$ in
$\mathbb{R}^{d}$ for some fixed $d$. Assume that $m\leq n$. There exists a
constant $\mu\in(0,1)$ such that (i) one can decide whether
$d_{F}(\sigma,\tau)\leq\delta$ in $O(mn(\log\log m)^{2+\mu}/\log^{1+\mu}m)$
expected time, and (ii) one can compute $d_{F}(\sigma,\tau)$ in $O(mn(\log\log
m)^{2+\mu}\log n/\log^{1+\mu}m)$ expected time. Hence, if
$m=\Omega(n^{\varepsilon})$ for any fixed $\varepsilon\in(0,1]$, one can
compute $d_{F}(\sigma,\tau)$ in $o(mn)$ time.

##  7 Conclusion

A natural question is whether one can shave more log factors from the running
time. Our running time is not deterministic because of the expected
construction time bound of the point location data structure in Theorem 2. It
may be possible to design a deterministic construction algorithm.

##  Appendix A Polynomials for predicates

We restate the predicates we are going to implement as follows.

$P_{1}(i,j)=\text{true}$ $\iff$ $d(w_{j},v_{i}v_{i+1})\leq\delta$
$P_{2}(i,j)=\text{true}$ $\iff$ $d(v_{i},w_{j}w_{j+1})\leq\delta$
$P_{3}(i,j,j^{\prime})=\text{true}$ $\iff$ $\text{neither $s^{\prime}_{j,i}$
nor $s^{\prime}_{j^{\prime},i}$ is
null}\,\wedge\,s^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}s^{\prime}_{j^{\prime},i}$
$P_{4}(i,i^{\prime},j)=\text{true}$ $\iff$ $\text{neither $s_{i,j}$ nor
$s_{i^{\prime},j}$ is
null}\,\wedge\,s_{i,j}\leq_{w_{j}w_{j+1}}s_{i^{\prime},j}$
$P_{5}(i,j,j^{\prime})=\text{true}$ $\iff$ $\text{neither $e^{\prime}_{j,i}$
nor $e^{\prime}_{j^{\prime},i}$ is
null}\,\wedge\,e^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}e^{\prime}_{j^{\prime},i}$
$P_{6}(i,i^{\prime},j)=\text{true}$ $\iff$ $\text{neither $e_{i,j}$ nor
$e_{i^{\prime},j}$ is
null}\,\wedge\,e_{i,j}\leq_{w_{j}w_{j+1}}e_{i^{\prime},j}$
$P_{7}(i,j,j^{\prime})=\text{true}$ $\iff$ $\text{neither $s^{\prime}_{j,i}$
nor $e^{\prime}_{j^{\prime},i}$ is
null}\,\wedge\,s^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}e^{\prime}_{j^{\prime},i}$
$P_{8}(i,i^{\prime},j)=\text{true}$ $\iff$ $\text{neither $s_{i,j}$ nor
$e_{i^{\prime},j}$ is
null}\,\wedge\,s_{i,j}\leq_{w_{j}w_{j+1}}e_{i^{\prime},j}$

Table 2: Predicates for determining the signature of a box.

We describe how to implement them by polynomials. We view $\delta$ and the
coordinates of $v_{i},v_{i+1},v_{i^{\prime}}$ as fixed coefficienets and the
coordinates of $w_{j},w_{j+1},w_{j^{\prime}}$ as variables.

$P_{1}(i,j)$. We present several polynomials to implement $P_{1}(i,j)$. We use
$\langle\nu,\nu^{\prime}\rangle$ to denote the inner product of vectors $\nu$
and $\nu^{\prime}$. Let $\text{aff}(v_{i}v_{i+1})$ be the oriented line that
contains $v_{i}v_{i+1}$ and has the same orientation as $v_{i}v_{i+1}$. We
first write $d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}\cdot\lVert
v_{i}-v_{i+1}\rVert^{2}$ as a polynomial.

$\displaystyle d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}\cdot\lVert
v_{i}-v_{i+1}\rVert^{2}$ (1) $\displaystyle=$ $\displaystyle\lVert
w_{j}-v_{i+1}\rVert^{2}\cdot\lVert v_{i}-v_{i+1}\rVert^{2}-\langle
w_{j}-v_{i+1},v_{i}-v_{i+1}\rangle^{2}.$

The first polynomial $f_{1,1}^{i,j}$ compares the distance
$d(w_{j},\text{aff}(v_{i}v_{i+1}))$ with $\delta$.

$\displaystyle f_{1,1}^{i,j}$
$\displaystyle=\bigl{(}d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}-\delta^{2}\bigr{)}\cdot\lVert
v_{i}-v_{i+1}\rVert^{2}$ $\displaystyle=\lVert
w_{j}-v_{i+1}\rVert^{2}\cdot\lVert v_{i}-v_{i+1}\rVert^{2}-\langle
w_{j}-v_{i+1},v_{i}-v_{i+1}\rangle^{2}-\delta^{2}\cdot\|v_{i}-v_{i+1}\|^{2}.$

Since $\lVert v_{i}-v_{i+1}\rVert^{2}$ is positive, we have
$d(w_{j},\text{aff}(v_{i}v_{i+1}))\leq\delta$ if and only if
$f_{1,1}^{i,j}\leq 0$. Therefore, if $f_{1,1}^{i,j}>0$, then
$P_{1}(i^{\prime},j^{\prime})$ is false. If $f_{1,1}^{i,j}\leq 0$, we use the
following two polynomials to check whether the projection of $w_{j}$ in
$\text{aff}(v_{i}v_{i+1})$ lies on $v_{i}v_{i+1}$.

$f_{1,2}^{i,j}=\langle w_{j}-v_{i},v_{i+1}-v_{i}\rangle,\quad\quad
f_{1,3}^{i,j}=\langle w_{j}-v_{i+1},v_{i}-v_{i+1}\rangle.$

The projection of $w_{j}$ in $\text{aff}(v_{i}v_{i+1})$ lies on $v_{i}v_{i+1}$
if and only if $f_{1,2}^{i,j}\geq 0$ and $f_{1,3}^{i,j}\geq 0$. Hence, if
$f_{1,1}^{i,j}\leq 0$, $f_{1,2}^{i,j}\geq 0$, and $f_{1,3}^{i,j}\geq 0$, then
$P_{1}(i,j)$ is true. When $f_{1,2}^{i,j}<0$ or $f_{1,3}^{i,j}<0$, we use the
following polynomials to compare $d(w_{j},v_{i})$ and $d(w_{j},v_{i+1})$ with
$\delta$.

$f_{1,4}^{i,j}=\lVert w_{j}-v_{i}\rVert^{2}-\delta^{2},\quad\quad
f_{1,5}^{i,j}=\lVert w_{j}-v_{i+1}\rVert^{2}-\delta^{2}.$

If $f_{1,1}^{i,j}\leq 0$ and $f_{1,2}^{i,j}<0$, then $v_{i}$ is the nearest
point in $v_{i}v_{i+1}$ to $w_{j}$. So, $P_{1}(i,j)$ is true if and only if
$f_{1,4}^{i,j}\leq 0$. Similarly, in the case that $f_{1,1}^{i,j}\leq 0$ and
$f_{1,3}^{i,j}<0$, $P_{1}(i,j)$ is true if and only if $f_{1,5}^{i,j}\leq 0$.

$P_{2}(i,j)$. We can define polynomials $f_{2,1}^{i,j}$, $f_{2,2}^{i,j}$,
$f_{2,3}^{i,j}$, $f_{2,4}^{i,j}$, and $f_{2,5}^{i,j}$ to implement
$P_{2}(i,j)$ in a way analogous to the definitions of polynomials for
$P_{1}(i,j)$.

$P_{3}(i,j,j^{\prime})$. We first check whether $P_{1}(i,j)$ and
$P_{1}(i,j^{\prime})$ are true according to the signs of polynomials designed
for $P_{1}(i,j)$ and $P_{1}(i,j^{\prime})$. If either $P_{1}(i,j)$ or
$P_{1}(i,j^{\prime})$ is false, then either $s^{\prime}_{j,i}$ or
$s^{\prime}_{j^{\prime},i}$ is null. Hence, $P_{3}(i,j,j^{\prime})$ is false.
Suppose that both $P_{1}(i,j)$ and $P_{1}(i,j^{\prime})$ are true. Let
$\tilde{s}^{\prime}_{j,i}$ be the start of the oriented segment
$\mathcal{B}_{w_{j}}\cap\mathrm{aff}(v_{i}v_{i+1})$. Let
$\tilde{s}^{\prime}_{j^{\prime},i}$ be the start of the oriented segment
$\mathcal{B}_{w_{j^{\prime}}}\cap\mathrm{aff}(v_{i}v_{i+1})$. We use several
polynomials to check whether $\tilde{s}^{\prime}_{j,i}$ is not behind
$\tilde{s}^{\prime}_{j^{\prime},i}$ in the direction of $v_{i+1}-v_{i}$.

We use the polynomial $f_{3,1}^{i,j,j^{\prime}}$ below to check whether the
order of the projections of $w_{j}$ and $w_{j^{\prime}}$ in
$\mathrm{aff}(v_{i}v_{i+1})$ is consistent with the direction of
$v_{i+1}-v_{i}$.

$f_{3,1}^{i,j,j^{\prime}}=\langle w_{j^{\prime}}-w_{j},v_{i+1}-v_{i}\rangle.$

Let $z_{1}$ be the distance between the projection of $w_{j}$ in
$\text{aff}(v_{i}v_{i+1})$ and the projection of $w_{j^{\prime}}$ in
$\text{aff}(v_{i}v_{i+1})$. Let $z_{2}$ be the distance between
$\tilde{s}^{\prime}_{j,i}$ and the projection of $w_{j}$ in
$\text{aff}(v_{i}v_{i+1})$. Let $z_{3}$ be the distance between
$\tilde{s}^{\prime}_{j^{\prime},i}$ and the projection of $w_{j^{\prime}}$ in
$\text{aff}(v_{i}v_{i+1})$.

If $f_{3,1}^{i,j,j^{\prime}}\geq 0$, the projection of $w_{j}$ is not behind
the projection of $w_{j^{\prime}}$. In this case, $\tilde{s}^{\prime}_{j,i}$
is not behind $\tilde{s}^{\prime}_{j^{\prime},i}$ if and only if
$z_{1}+z_{2}\geq z_{3}$. See Figure. 2 for illustration. We write $z_{1}^{2}$,
$z_{2}^{2}$ and $z_{3}^{2}$ as follows:

$\displaystyle z_{1}^{2}$ $\displaystyle=\langle
w_{j^{\prime}}-w_{j},v_{i+1}-v_{i}\rangle^{2}\cdot\|v_{i+1}-v_{i}\|^{-2},$
$\displaystyle z_{2}^{2}$
$\displaystyle=\delta^{2}-d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2},$
$\displaystyle z_{3}^{2}$
$\displaystyle=\delta^{2}-d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}.$

Figure 2: Illustration for the case that the projection of $w_{j}$ is not
behind that of $w_{j^{\prime}}.$

We present several polynomials to check whether $z_{1}+z_{2}\geq z_{3}$. Since
$z_{1}$, $z_{2}$ and $z_{3}$ are non-negative, $z_{1}+z_{2}\geq z_{3}$ if and
only if $z_{1}^{2}+z_{2}^{2}+2z_{1}z_{2}\geq z_{3}^{2}$. By moving
$z_{1}^{2}+z_{2}^{2}$ to the right-hand side, we get $2z_{1}z_{2}\geq
z_{3}^{2}-z_{1}^{2}-z_{2}^{2}$. We use a polynomial $f_{3,2}^{i,j,j^{\prime}}$
to represent $(z_{3}^{2}-z_{1}^{2}-z_{2}^{2})\|v_{i+1}-v_{i}\|^{2}$.

$f_{3,2}^{i,j,j^{\prime}}=\bigl{(}d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}-d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}\bigr{)}\|v_{i+1}-v_{i}\|^{2}-\langle
w_{j^{\prime}}-w_{j},v_{i+1}-v_{i}\rangle^{2}.$

The terms $d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}\|v_{i+1}-v_{i}\|^{2}$ and
$d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}\|v_{i+1}-v_{i}\|^{2}$ are
expanded as in (1). As a shorthand, we do not explicitly show the expansion.

Since $\|v_{i+1}-v_{i}\|>0$, we have $z_{3}^{3}-z_{1}^{2}-z_{2}^{2}\leq 0$ if
and only if $f_{3,2}^{i,j,j^{\prime}}\leq 0$. Since $2z_{1}z_{2}\geq 0$, if
$f_{3,2}^{i,j,j^{\prime}}\leq 0$, we always have $2z_{1}z_{2}\geq
z_{3}^{2}-z_{1}^{2}-z_{2}^{2}$. It means that $\tilde{s}^{\prime}_{j,i}$ is
not behind $\tilde{s}^{\prime}_{j^{\prime},i}$.

Suppose that $f_{3,2}^{i,j,j^{\prime}}>0$. The inequality $z_{1}+z_{2}\geq
z_{3}$ holds if and only if
$4z_{1}^{2}z_{2}^{2}\geq(z_{3}^{2}-z_{1}^{2}-z_{2}^{2})^{2}$, i.e.
$4z_{1}^{2}z_{2}^{2}-(z_{3}^{2}-z_{1}^{2}-z_{2}^{2})^{2}\geq 0$. We use a
polynomial $f_{3,3}^{i,j,j^{\prime}}$ to denote
$(4z_{1}^{2}z_{2}^{2}-(z_{3}^{2}-z_{1}^{2}-z_{2}^{2})^{2})\|v_{i+1}-v_{i}\|^{4}$.

$f_{3,3}^{i,j,j^{\prime}}=4\langle
w_{j^{\prime}}-w_{j},v_{i+1}-v_{i}\rangle^{2}\bigl{(}\delta^{2}-d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}\bigr{)}\|v_{i+1}-v_{i}\|^{2}-(f_{3,2}^{i,j,j^{\prime}})^{2}$

Since $\|v_{i+1}-v_{i}\|>0$, $\tilde{s}^{\prime}_{j,i}$ is not behind
$\tilde{s}^{\prime}_{j^{\prime},i}$ if and only if
$f_{3,3}^{i,j,j^{\prime}}\geq 0$.

We then consider the case that $f_{3,1}^{i,j,j^{\prime}}<0$, i.e., the
projection of $w_{j}$ is behind the projection of $w_{j^{\prime}}$. In this
case, $\tilde{s}^{\prime}_{j,i}$ is not behind
$\tilde{s}^{\prime}_{j^{\prime},i}$ if and only if $z_{2}>z_{1}+z_{3}$. We can
define polynomials $f_{3,4}^{i,j,j^{\prime}}$ and $f_{3,5}^{i,j,j^{\prime}}$
to check whether $z_{2}>z_{1}+z_{3}$ in the same way as how we check
$z_{1}+z_{2}\geq z_{3}$. We finish defining the polynomials to determine
whether $\tilde{s}^{\prime}_{j,i}$ is not behind
$\tilde{s}^{\prime}_{j^{\prime},i}$ when $s^{\prime}_{j,i}$ and
$s^{\prime}_{j^{\prime},i}$ are not null.

We describe how to determine whether
$s^{\prime}_{j,i}=s^{\prime}_{j^{\prime},i}$ or
$s^{\prime}_{j,i}\leq_{v_{i}v_{i+1}}s^{\prime}_{j^{\prime},i}$. Given that
both $s^{\prime}_{j,i}$ and $s^{\prime}_{j^{\prime},i}$ are not null, if
$d(v_{i},w_{j})>\delta$, then $s^{\prime}_{j,i}=\tilde{s}^{\prime}_{j,i}$;
otherwise, $s^{\prime}_{j,i}=v_{i}$. Similarly, if
$d(v_{i},w_{j^{\prime}})>\delta$, then
$s^{\prime}_{j^{\prime},i}=\tilde{s}^{\prime}_{j^{\prime},i}$; otherwise,
$s^{\prime}_{j^{\prime},i}=v_{i}$. These decisions can be made using the
following polynomials.

$f_{3,6}^{i,j}=\|v_{i}-w_{j}\|^{2}-\delta^{2},\quad\quad
f_{3,7}^{i,j^{\prime}}=\|v_{i}-w_{j^{\prime}}\|^{2}-\delta^{2}.$

Using these decisions, the comparison between $s^{\prime}_{j,i}$ and
$s^{\prime}_{j^{\prime},i}$ falls into the following four cases. If
$s^{\prime}_{j,i}=\tilde{s}^{\prime}_{j,i}$ and
$s^{\prime}_{j^{\prime},i}=\tilde{s}^{\prime}_{j^{\prime},i}$, we are done. If
$s^{\prime}_{j,i}=v_{i}$ and
$s^{\prime}_{j^{\prime},i}=\tilde{s}^{\prime}_{j^{\prime},i}$, then
$P_{3}(i,j,j^{\prime})$ is true because $v_{i}$ is not behind any point on
$v_{i}v_{i+1}$ along $v_{i}v_{i+1}$. If $s^{\prime}_{j,i}\not=v_{i}$ and
$s^{\prime}_{j^{\prime},i}=v_{i}$, then
$s^{\prime}_{j,i}=\tilde{s}^{\prime}_{j,i}$ is an interior point of
$v_{i}v_{i+1}$, which makes $P_{3}(i,j,j^{\prime})$ false. In the remaining
case, both $s^{\prime}_{j,i}$ and $s^{\prime}_{j^{\prime},i}$ are $v_{i}$, so
$P_{3}(i,j,j^{\prime})$ is true.

$P_{4}(i,i^{\prime},j),P_{5}(i,j,j^{\prime}),P_{6}(i,i^{\prime},j),P_{7}(i,j,j^{\prime}),P_{8}(i,i^{\prime},j)$.
We can define polynomials to implement these predicate in a way analogous to
the definitions of the polynomials for $P_{3}(i,j,j^{\prime})$.

##  Appendix B Predicates and polynomials for Lemma 7

We want to process $v_{a_{k}},\ldots,v_{a_{k+1}}$ into a data structure that
takes a query point $y$ on a query edge $w_{j}w_{j+1}$ and locate the
immediate predecessor of $y$ in the sorted order of
$s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+1},j},e_{a_{k+1},j}$ along
$w_{j}w_{j+1}$. The truth values of the following predicates determine the
query result.

$P_{9}(i,j)=\text{true}$ $\iff$ $d(v_{i},w_{j}w_{j+1})\leq\delta$
$P_{10}(i,j)=\text{true}$ $\iff$ $\text{$s_{i,j}$ is not
null}\,\wedge\,y\leq_{w_{j}w_{j+1}}s_{i,j}$ $P_{11}(i,j)=\text{true}$ $\iff$
$\text{$e_{i,j}$ is not null}\,\wedge\,y\leq_{w_{j}w_{j+1}}e_{i,j}$
$P_{12}(i,j)=\text{true}$ $\iff$ $s_{i,j}$ is not null and $y=s_{i,j}$
$P_{13}(i,j)=\text{true}$ $\iff$ $e_{i,j}$ is not null and $y=e_{i,j}$

Table 3: There are $O(\alpha)$ predicates over all $i\in B_{k}$.

When we invoke a $B_{k}$-coder and perform the query described above with
$y=\ell_{a_{k},j}$ during dynamic programming, we already have the signature
of the box that involves $B_{k}$ and $w_{j}w_{j+1}$. The signature $\phi$ of
the column $j$ of this box tells us the rank values of
$s_{a_{k},j},e_{a_{k},j},\ldots,s_{a_{k+1},j},e_{a_{k+1},j}$ along
$w_{j}w_{j+1}$. Therefore, the truth values of $P_{9},P_{10},P_{11}$ tell us
the $s_{i,j}$ with the lowest rank value that lies in front of $y$, which
makes $s_{i,j}$ the immediate predecessor. The truth values of $P_{12}$ and
$P_{13}$ tell us whether $y$ is equal to this immediate predecessor.

Next, we construct a set of polynomials for these predicates. We will handle
$P_{10}(i,j)$ and $P_{12}(i,j)$ together and $P_{11}(i,j)$ and $P_{13}(i,j)$
together.

$P_{9}(i,j)$. The predicate $P_{9}(i,j)$ is equivalent to $P_{2}(i,j)$. We can
use the polynomials $f_{2,1}^{i,j}$, $f_{2,2}^{i,j}$, $f_{2,3}^{i,j}$,
$f_{2,4}^{i,j}$, and $f_{2,5}^{i,j}$ to implement it.

$P_{10}(i,j)$ and $P_{12}(i,j)$. We first check whether $P_{9}(i,j)$ is true
according to the signs of polynomials designed for $P_{9}(i,j)$. If
$P_{9}(i,j)$ is false, then $s_{i,j}$ is null. Hence, $P_{10}(i,j)$ and
$P_{12}(i,j)$ are false. Suppose that $P_{9}(i,j)$ is true. In this case,
$B_{v_{i}}\cap w_{j}w_{j+1}\not=\emptyset$. We use the following polynomial to
check whether $y$ is behind the projection of $v_{i}$ in
$\mathrm{aff}(w_{j}w_{j+1})$ in the direction of $w_{j+1}-w_{j}$.

$f_{10,1}^{i,j}=\langle v_{i}-y,w_{j+1}-w_{j}\rangle.$

Figure 3: Illustration for the case that the projection of $v_{i}$ is not in
$w_{j}w_{j+1}$ and $y$ is behind the projection of $v_{i}$.

If $f_{10,1}^{i,j}<0$, $y$ is behind the projection of $v_{i}$ in
$\mathrm{aff}(w_{j}w_{j+1})$. We use the following two polynomials to check
whether the projection of $v_{i}$ in $\mathrm{aff}(w_{j}w_{j+1})$ lies on
$w_{j}w_{j+1}$.

$f_{10,2}^{i,j}=\langle v_{i}-w_{j},w_{j+1}-w_{j}\rangle,\quad\quad
f_{10,3}^{i,j}=\langle v_{i}-w_{j+1},w_{j}-w_{j+1}\rangle.$

When $f_{10,2}^{i,j}\geq 0$ and $f_{10,3}^{i,j}\geq 0$, the projection of
$v_{i}$ is in $w_{j}w_{j+1}$ as well. In this case, $s_{i,j}$ must not be
behind the projection of $v_{i}$. As a result, $y$ is behind $s_{i,j}$, so
both $P_{10}(i,j)$ and $P_{12}(i,j)$ are false. In the other case, the
projection of $v_{i}$ is not in $w_{j}w_{j+1}$. Since $y\in w_{j}w_{j+1}$ and
$y$ is behind the projection of $v_{i}$, the nearest point in $w_{j}w_{j+1}$
to $v_{i}$ is $w_{j}$. Since $B_{v_{i}}\cap w_{j}w_{j+1}\not=\emptyset$,
$s_{i,j}$ is equal to $w_{j}$. See Figure. 3 for an illustration. As a result,
we need to check whether $y$ is behind $w_{j}$ in the direction of
$w_{j+1}-w_{j}$ by the following polynomial:

$f_{10,4}^{i,j}=\langle y-w_{j},w_{j+1}-w_{j}\rangle.$

If $f_{10,4}^{i,j}>0$, then $y$ is behind $s_{i,j}$, so both $P_{10}(i,j)$ and
$P_{12}(i,j)$ are false. If $f_{10,4}^{i,j}=0$, then $y$ is equal to
$s_{i,j}$, so both $P_{10}(i,j)$ and $P_{12}(i,j)$ are true.

If $f_{10,1}^{i}\geq 0$, $y$ is not behind the projection of $v_{i}$ in
$\mathrm{aff}(w_{j}w_{j+1})$ in the direction of $w_{j+1}-w_{j}$. Since $y\in
w_{j}w_{j+1}$ and $B_{v_{i}}\cap w_{j}w_{j+1}\not=\emptyset$, it must hold
that $B_{v_{i}}\cap yw_{j+1}\not=\emptyset$. In this case, $y$ is not behind
$s_{i,j}$ if and only if $d(v_{i},y)\geq\delta$. We use the following
polynomial to compare $d(v_{i},y)$ and $\delta$.

$f_{10,5}^{i,j}=\|v_{i}-y\|^{2}-\delta^{2}.$

If $f_{10,5}^{i,j}\geq 0$, the distance between $v_{i}$ and $y$ is at least
$\delta$, then $P_{10}(i,j)$ is true; otherwise, $P_{10}(i,j)$ is false. If
$f_{10,5}^{i,j}=0$, then $P_{12}(i,j)$ is true; otherwise, $P_{12}(i,j)$ is
false.

$P_{11}(i,j)$ and $P_{13}(i,j)$. We can define polynomials to implement
$P_{11}(i,j)$ and $P_{13}(i,j)$ in a way analogous to the definitions of
polynomials for $P_{10}(i,j)$ and $P_{12}(i,j)$.

## References

  * [1] Peyman Afshani and Anne Driemel.  On the complexity of range searching among curves.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 898–917, 2018.
  * [2] 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.
  * [3] Helmut Alt.  The Computational Geometry of Comparing Shapes, pages 235–248.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
  * [4] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  International Journal of Computational Geometry and Applications, 5:75–91, 1995.
  * [5] Helmut Alt, Christian Knauer, and Carola Wenk.  Comparsion of distance measures for planar curves.  Algorithmica, 38:45–58, 2004.
  * [6] Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk.  Fréchet distance for curves, revisited.  In Proceedings of the 14th Annual European Symposium on Algorithms, pages 52–63. Springer, 2006.
  * [7] Saugata Basu, Richard Pollack, and Marie-Françoise Roy.  On computing a set of points meeting every cell defined by a family of polynomials on a variety.  Journal of Complexity, 13:28–37, 1995.
  * [8] Lotte Blank and Anne Driemel.  A faster algorithm for the Fréchet distance in 1d for the imbalanced case.  arXiv preprint arXiv:2404.18738, 2024.
  * [9] Karl Bringmann.  Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails.  In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661–670. IEEE, 2014.
  * [10] Karl Bringmann and Marvin Künnemann.  Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds.  In Proceedings of International Symposium on Algorithms and Computation, pages 517–528. Springer, 2015.
  * [11] Karl Bringmann and Wolfgang Mulzer.  Approximiability of the discrete Fréchet distance.  In Proceedings of the International Symposium on Computational Geometry, pages 739–753, 2015.
  * [12] Frederik Brüning and Anne Driemel.  Simplified and improved bounds on the VC-dimension for elastic distance measures.  arXiv, 2023.
  * [13] Kevin Buchin, Maike Buchin, David Duran, Brittany Terese Fasy, Roel Jacobs, Vera Sacristan, Rodrigo I Silveira, Frank Staals, and Carola Wenk.  Clustering trajectories for map construction.  In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1–10, 2017.
  * [14] Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo.  Detecting commuting patterns by clustering subtrajectories.  International Journal of Computational Geometry & Applications, 21(03):253–282, 2011.
  * [15] Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer.  Four soviets walk the dog—with an application to Alt’s conjecture.  In Proceedings of the Annual ACM-SIAM Symposium on Discrete algorithms, pages 1399–1413. SIAM, 2014.
  * [16] 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 Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2887–2901. SIAM, 2019.
  * [17] Timothy M Chan.  More logarithmic-factor speedups for 3SUM,(median,+)-convolution, and some geometric 3SUM-hard problems.  In Proceedings of the ACM-SIAM Symposium on Discreete Algorithms, pages 881–897, 2018.
  * [18] Timothy M Chan and Zahed Rahmati.  An improved approximation algorithm for the discrete Fréchet distance.  Information Processing Letters, 138:72–74, 2018.
  * [19] Siu-Wing Cheng and Haoqiang Huang.  Solving Fréchet distance problems by algebraic geometric methods.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 4502–4513. SIAM, 2023.
  * [20] Connor Colombe and Kyle Fox.  Approximating the (continuous) Fréchet distance.  In Proceedings of International Symposium on Computational Geometry. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [21] Anne Driemel, Sariel Har-Peled, and Carola Wenk.  Approximating the Fréchet distance for realistic curves in near linear time.  Discrete & Computational Geometry, 48:94–127, 2012.
  * [22] Anne Driemel, André’ Nusser, Jeff M. Phillips, and Ioannis Psarros.  The VC dimension of metric balls under Fréchet and Hausdorff distances.  Discrete & Computational Geometry, 66:1351–1381, 2021.
  * [23] Thomas Eiter and Heikki Mannila.  Computing the discrete Fréchet distance.  Technical report, Vienna University of Technology, 1994.
  * [24] Esther Ezra, Sariel Har-Peled, Haim Kaplan, and Micha Sharir.  Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location.  Discrete & Computational Geometry, 64(1):109–173, 2020.
  * [25] Ari Freund.  Improved subquadratic 3SUM.  Algorithmica, 77(2):440–456, 2017.
  * [26] Michael Godau.  A natural metric for curves - computing the distance for polygonal chains and approximation algorithms.  In Proceedings of the Symposium on Theoretical Aspects of Computer Science, 1991.
  * [27] Omer Gold and Micha Sharir.  Improved bounds for 3SUM, $k$-SUM, and linear degenerarcy.  In Proceedings of the European Symposium on Algorithms, pages 42:1–13, 2017.
  * [28] Omer Gold and Micha Sharir.  Dynamic time warping and geometric edit distance: Breaking the quadratic barrier.  ACM Transactions on Algorithms, 14(4):1–17, 2018.
  * [29] Allan Grønlund and Seth Pettie.  Threesomes, degenerates, and love triangles.  Journal of the ACM, 65(4):22:1–22:25, 2018.
  * [30] Joachim Gudmundsson, Majid Mirzanezhad, Ali Mohades, and Carola Wenk.  Fast Fréchet distance between curves with long edges.  In Proceedings of the 3rd International Workshop on Interactive and Spatial Computing, pages 52–58, 2018.
  * [31] Daniel M. Kane, Shachar Lovett, and Shay Moran.  Near-optimal linear decision trees for $k$-SUM and related problems.  In Proceedings of the ACM Symposium on Theory of Computing, pages 554–563, 2018.
  * [32] Richard Pollack and Marie-Françoise Roy.  On the number of cells defined by a set of polynomials.  Comptes rendus de l’Académie des sciences. Série 1, Mathématique, 316(6):573–577, 1993.
  * [33] Thijs van der Horst and Tim Ophelders.  Faster Fréchet Distance Approximation Through Truncated Smoothing.  In Proceedings of the 40th International Symposium on Computational Geometry, pages 63:1–63:15, 2024.
  * [34] Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann.  A subquadratic $n^{\varepsilon}$-approximation for the continuous Fréchet distance.  In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1759–1776. SIAM, 2023.