# Solving Fréchet Distance Problems by Algebraic Geometric Methods††thanks:
Research supported by the Research Grants Council, Hong Kong, China (project
no. 16208923).

Siu-Wing Cheng111Department of Computer Science and Engineering, HKUST, Hong
Kong. Email<EMAIL_ADDRESS>Haoqiang Huang222Department of Computer Science
and Engineering, HKUST, Hong Kong. Email<EMAIL_ADDRESS>
###### Abstract

We study several polygonal curve problems under the Fréchet distance via
algebraic geometric methods. Let $\mathbb{X}_{m}^{d}$ and $\mathbb{X}_{k}^{d}$
be the spaces of all polygonal curves of $m$ and $k$ vertices in
$\mathbb{R}^{d}$, respectively. We assume that $k\leq m$. Let
$\mathcal{R}^{d}_{k,m}$ be the set of ranges in $\mathbb{X}_{m}^{d}$ for all
possible metric balls of polygonal curves in $\mathbb{X}_{k}^{d}$ under the
Fréchet distance. We prove a nearly optimal bound of $O(dk\log(km))$ on the VC
dimension of the range space $(\mathbb{X}_{m}^{d},\mathcal{R}_{k,m}^{d})$,
improving on the previous $O(d^{2}k^{2}\log(dkm))$ upper bound and approaching
the current $\Omega(dk\log k)$ lower bound. Our upper bound also holds for the
weak Fréchet distance. We also obtain exact solutions that are hitherto
unknown for the curve simplification, range searching, nearest neighbor
search, and distance oracle problems.

##  1 Introduction.

The Fréchet distance, denoted by $d_{F}$, is a popular distance metric to
measure the similarity between curves that has been used in various
applications such as map construction, trajectory analysis, protein structure
analysis, and handwritten document processing (e.g. [11, 12, 41, 45]).

We use $\mathbb{X}_{\ell}^{d}$ to denote the space of all polygonal curves of
$\ell$ vertices in $\mathbb{R}^{d}$. Given a curve
$\gamma\in\mathbb{X}_{\ell}^{d}$, we call $\ell$ the _size_ of $\gamma$ and
denote it by $|\gamma|$. A parameterization of a curve
$\tau\in\mathbb{X}_{m}^{d}$ is a function $\rho:[0,1]\to\mathbb{R}^{d}$ such
that $\rho(t)$ moves monotonically from the beginning of $\tau$ to its end as
$t$ increases from 0 to 1. It is possible that $\rho(t_{1})=\rho(t_{2})$ for
some $t_{1}$ and $t_{2}$ that are different. Given a parameterization
$\varrho$ of another curve $\sigma\in\mathbb{X}_{k}^{d}$, the pair
$(\rho,\varrho)$ form a matching $\cal M$ in the sense that $\rho(t)$ is
matched to $\varrho(t)$ for all $t\in[0,1]$. Let $d_{\cal
M}(\sigma,\tau)=\max_{t\in[0,1]}d(\varrho(t),\rho(t))$. A _Fréchet matching_
is a matching that minimizes $d_{\cal M}(\sigma,\tau)$. We call the
corresponding distance the _Fréchet distance_ of $\sigma$ and $\tau$, denoted
by $d_{F}(\sigma,\tau)$. A variant is to drop the monotonicity constraint on
the parameterization of a curve, i.e., $\rho(t)$ is allowed to move back and
forth continuously along $\tau$ in its movement from the beginning of $\tau$
to its end. The corresponding distance is known as the _weak Fréchet distance_
of $\sigma$ and $\tau$, denoted by $\hat{d}_{F}(\sigma,\tau)$. Clearly,
$\hat{d}_{F}(\sigma,\tau)\leq d_{F}(\sigma,\tau)$. Alt and Godau developed the
first $O(km\log(km))$-time algorithms to compute $d_{F}(\sigma,\tau)$ and
$\hat{d}_{F}(\sigma,\tau)$ [4].

There are many algorithmic challenges that arise from the analysis of curves
and trajectories. Range searching under the Fréchet distance was made by ACM
SIGSPATIAL in 2017 a software challenge [48]. There has been extensive
research on curve simplification [3, 7, 8, 18, 21, 36, 38, 39, 46, 47],
clustering [13, 14, 18, 23, 43], and nearest neighbor search [17, 25, 26, 28,
27, 31, 40, 42]. Range searching has also been studied [1]. In this paper, we
use algebraic geometric methods to solve Fréchet distance problems. Algebraic
geometric tools have hardly been used before. Afshani and Driemel [1] employed
a semialgebraic range searching solution in $\mathbb{R}^{2}$, but we go much
further to use arrangements of zero sets of polynomials in higher dimensions.
We will deal with input curve(s) in $\mathbb{X}_{m}^{d}$ and output/query
curve in $\mathbb{X}_{k}^{d}$. We assume that $k\leq m$. The condition that is
most favorable for our results is that $k\ll m$; it is a natural goal for
curve simplification; the condition of $k\ll m$ is also natural for query
problems when the query curve is a sketch provided by the user in 2D or 3D, or
a short sequence of key configurations in higher dimensions.

###  1.1 Previous work.

VC dimension. Let $\mathcal{R}^{d}_{k,m}$ be the set of ranges in
$\mathbb{X}_{m}^{d}$ for all possible metric balls of polygonal curves in
$\mathbb{X}_{k}^{d}$ under $d_{F}$. That is,
$\mathcal{R}_{k,m}^{d}=\\{B_{F}(\sigma,r):r\in\mathbb{R}_{\geq
0},\sigma\in\mathbb{X}_{k}^{d}\\}$, where
$B_{F}(\sigma,r)=\\{\tau\in\mathbb{X}_{m}^{d}:d_{F}(\sigma,\tau)\leq r\\}$.
Driemel et al. [24] showed that the VC dimension of the range space
$\bigl{(}\mathbb{X}_{m}^{d},\mathcal{R}_{k,m}^{d}\bigr{)}$ is
$O(d^{2}k^{2}\log(dkm))$. They also proved a lower bound of
$\Omega\bigl{(}\max\\{dk\log k,\log(dm)\\}\bigr{)}$. For $\hat{d}_{F}$, the
same lower bound holds and the upper bound improves to $O(d^{2}k\log(dkm))$.
Recently and independently, Brüning and Driemel [10] obtained the same
$O(dk\log(km))$ bound for the VC dimension of
$\bigl{(}\mathbb{X}_{m}^{d},\mathcal{R}_{k,m}^{d}\bigr{)}$ using arguments
that are similar to ours. They also proved an $O(dk\log(km))$ bound for the VC
dimension under Hausdorff distance and an $O(\min\\{dk^{2}\log m,dkm\log
k\\})$ bound for the VC dimension under dynamic time warping.

Driemel et al. [24] discussed several applications of the VC dimension bound.
Let $T$ be a set of input curves from $\mathbb{X}_{m}^{d}$. The VC dimension
bound allows us to draw a small random sample of $T$ of size that does not
depend on the cardinality of $T$ and only depends on $m$ logarithmically. This
random sample allows us to perform approximate range counting in $T$ for any
metric ball of any curve in $\mathbb{X}_{k}^{d}$. The random sample also helps
to construct a compact classifier for classifying a query curve in
$\mathbb{X}_{k}^{d}$ based on the curves in $T$.

Curve simplification. In 2D and 3D, the simplifications of region boundaries
and trajectories of moving agents find applications in geographical
information systems. One may simplify a time series of multidimensional data
to speed up subsequent processing.

Given any $\tau\in\mathbb{X}_{m}^{d}$ and any $r>0$, one problem is to find a
curve $\sigma$ with the minimum size such that $d_{F}(\sigma,\tau)\leq r$. Let
$\kappa(\tau,r)$ denote this minimum size. Guibas et al. [36] presented an
$O(m^{2}\log^{2}m)$-time exact algorithm in $\mathbb{R}^{2}$, but no exact
algorithm is known in higher dimensions. Agarwal et al. [3] showed how to
construct $\sigma$ in $O(m\log m)$ time such that $d_{F}(\sigma,\tau)\leq r$
and $|\sigma|\leq\kappa(\tau,r/2)$. Van de Kerkhof et al. [46] showed that for
any $\varepsilon\in(0,1)$, one can construct $\sigma$ in
$O(\varepsilon^{-O(1)}m^{2}\log m\log\log m)$ time such that
$d_{F}(\sigma,\tau)\leq(1+\varepsilon)r$ and $|\sigma|\leq
2\,\kappa(\tau,r)-2$. If the vertices of $\sigma$ must be vertices of $\tau$,
Van Kreveld et al. [47] showed that $|\sigma|$ can be minimized in
$O(|\sigma|m^{5})$ time. Later, Van de Kerkhof et al. [46] and Bringmann and
Chaudhury [8] improved the running time to $O(m^{3})$. If the vertices of
$\sigma$ must lie on $\tau$ but not necessarily at the vertices, Van de
Kerkhof et al. [46] showed that $|\sigma|$ can be minimized in $O(m)$-time in
$\mathbb{R}$; however, the problem is NP-hard in dimensions two or higher. The
results of Van de Kerkhof et al. [46] also hold for $\hat{d}_{F}$. In the case
that the vertices of $\sigma$ are unrestricted, Cheng and Huang [18] obtained
a bicriteria approximation scheme in $\mathbb{R}^{d}$: for any
$\alpha,\varepsilon\in(0,1)$, one can construct $\sigma$ in
$\tilde{O}\bigl{(}m^{O(1/\alpha)}\cdot(d/(\alpha\varepsilon))^{O(d/\alpha)}\bigr{)}$
time such that $d_{F}(\sigma,\tau)\leq(1+\varepsilon)r$ and
$|\sigma|\leq(1+\alpha)\cdot\kappa(\tau,r)$.

Another simplification problem is that given an integer $k\geq 2$, compute a
curve $\sigma\in\mathbb{X}_{k}^{d}$ that minimizes $d_{F}(\sigma,\tau)$. In
$\mathbb{R}^{d}$, if the vertices of $\sigma$ must be vertices of $\tau$,
Godau [32] showed how to solve the problem in $O(m^{4}\log m)$ time. He also
proved that the curve $\sigma$ returned by his algorithm satisfies
$d_{F}(\sigma,\tau)\leq 7\,\mathrm{opt}$, where opt is the minimum possible
Fréchet distance if the vertices of $\sigma$ are unrestricted. Subsequently,
Agarwal et al. [3] showed that the curve $\sigma$ returned by Godau’s
algorithm [32] satisfies $d_{F}(\sigma,\tau)\leq 4\,\mathrm{opt}$.

Range searching. Let $T$ be a set of $n$ curves in $\mathbb{X}_{m}^{d}$. Let
$k\geq 2$ be a given integer. The problem is to construct a data structure so
that for any $\sigma\in\mathbb{X}_{k}^{d}$ and any $r>0$, one can efficiently
retrieve every $\tau\in T$ that satisfies $d_{F}(\sigma,\tau)\leq r$. In
$\mathbb{R}^{2}$, assuming that $r$ is given for preprocessing and
$k=\log^{O(1)}n$, Afshani and Driemel [1] achieves an
$O\bigl{(}\sqrt{n}\log^{O(m^{2})}n\bigr{)}$ query time using
$O\bigl{(}n(\log\log n)^{O(m^{2})}\bigr{)}$ space. Let $S(n)$ and $Q(n)$ be
the space and query time of any range searching data structure for this
problem, respectively. Afshani and Driemel [1] also proved that
$S(n)=\Omega\bigl{(}\frac{n^{2}}{Q(n)^{2}}\bigr{)}\cdot\bigl{(}\frac{\log(n/Q(n))}{\log\log
n}\bigr{)}^{k-1}/2^{O(2^{k})}$ and
$S(n)=\Omega\bigl{(}\frac{n^{2}}{Q(n)^{2}}\bigr{)}\cdot\bigl{(}\frac{\log(n/Q(n))}{k^{3+o(1)}\log\log
n}\bigr{)}^{k-1-o(1)}$. De Berg et al. [19] considered the problem of counting
the number of inclusion-maximal subcurves of a curve
$\tau\in\mathbb{X}_{m}^{d}$ that are within a query radius $r$ from a query
segment $\ell$. For any $s\in[m,m^{2}]$, they achieve an
$\tilde{O}(m/\sqrt{s})$ query time using $\tilde{O}(s)$ space; however, the
count may include some subcurves at Fréchet distance up to $(2+3\sqrt{2})r$
from $\ell$.

Nearest neighbor. Let $T$ be a set of $n$ curves in $\mathbb{X}_{m}^{d}$. Let
$k\geq 2$ be a given integer. The problem is to construct a data structure so
that for any $\sigma\in\mathbb{X}_{k}^{d}$, its (approximate) nearest neighbor
under $d_{F}$ can be retrieved efficiently. No efficient exact solution is
known. A related question is the $(\lambda,r)$-ANN problem for any $\lambda>1$
and any $r>0$ that are given for preprocessing: for any query curve
$\sigma\in\mathbb{X}_{k}^{d}$, either find a curve $\tau\in T$ that satisfies
$d_{F}(\sigma,\tau)\leq\lambda r$, or report that $d_{F}(\sigma,\tau)>r$ for
all $\tau\in T$. Har-Peled et al. [37] showed that a $(\lambda,r)$-ANN data
structure can be converted into a $\lambda$-ANN data structure; the space and
query time only increase by some polylogarithmic factors.

Driemel and Psarros [25] developed $(\lambda,r)$-ANN data structures in
$\mathbb{R}$ with the following combinations of
$(\lambda,\text{space},\text{query time})$:
$\bigl{(}5+\varepsilon,O(mn)+n\cdot
O(\frac{1}{\varepsilon})^{k},O(k)\bigr{)}$,
$\bigl{(}2+\varepsilon,O(mn)+n\cdot
O(\frac{m}{k\varepsilon})^{k},O(2^{k}k)\bigr{)}$, and $\bigl{(}24k+1,O(n\log
n+mn),O(k\log n)\bigr{)}$. The last one is randomized with a failure
probability of $1/\text{poly}(n)$. Bringman et al. [9] improved these
combinations in $\mathbb{R}$: $\bigl{(}1+\varepsilon,n\cdot
O(\frac{m}{k\varepsilon})^{k},O(2^{k}k)\bigr{)}$, $(2+\varepsilon,n\cdot
O(\frac{m}{k\varepsilon})^{k},O(k)\bigr{)}$,
$\bigl{(}2+\varepsilon,O(mn)+n\cdot
O(\frac{1}{\varepsilon})^{k},O(2^{k}k)\bigr{)}$,
$\bigl{(}2+\varepsilon,O(mn),O(\frac{1}{\varepsilon})^{k+2}\bigr{)}$, and
$\bigl{(}3+\varepsilon,O(mn)+n\cdot
O(\frac{1}{\varepsilon})^{k},O(k)\bigr{)}$. Cheng and Huang [17] presented
$(1+\varepsilon,r)$-ANN solutions in $\mathbb{R}^{d}$. For $d\in\\{2,3\\}$,
the space and query time are $O(mn/\varepsilon)^{O(k)}\cdot\tilde{O}(k)$ and
$O(1/\varepsilon)^{O(k)}\cdot\tilde{O}(k)$, respectively. For $d\geq 4$, the
space and query time increase to
$\tilde{O}\bigl{(}k(mnd^{d}/\varepsilon^{d})^{O(k)}+(mnd^{d}/\varepsilon^{d})^{O(1/\varepsilon^{2})}\bigr{)}$
and
$\tilde{O}\bigl{(}k(mn)^{0.5+\varepsilon}/\varepsilon^{d}+k(d/\varepsilon)^{O(dk)}\bigr{)}$,
respectively. They also presented $(3+\varepsilon,r)$-ANN data structures with
query times of $\tilde{O}(k)$ for $d\in\\{2,3\\}$ and
$\tilde{O}\bigl{(}k(mn)^{0.5+\varepsilon}/\varepsilon^{d}\bigr{)}$ for $d\geq
4$.

Bringman et al. [9] proves that, conditioned on the orthogonal vector
hypothesis, one cannot achieve the following combinations of
$(\lambda,\text{space},\text{query time})$ for the $(\lambda,r)$-ANN problem
for any $\varepsilon,\varepsilon^{\prime}\in(0,1)$:
$(2-\varepsilon,\text{poly}(n),O(n^{1-\varepsilon^{\prime}}))$ in $\mathbb{R}$
when $1\ll k\ll\log n$ and $m=kn^{\Theta(1/k)}$,
$(3-\varepsilon,\text{poly}(n),O(n^{1-\varepsilon^{\prime}}))$ in $\mathbb{R}$
when $k=m=\Theta(\log n)$, and
$(3-\varepsilon,\text{poly}(n),O(n^{1-\varepsilon^{\prime}}))$ in
$\mathbb{R}^{2}$ when $1\ll k\ll\log n$ and $m=kn^{\Theta(1/k)}$. Approximate
nearest neighbor results are also known for the _discrete_ Fréchet distance
[28, 29, 31, 40].

Distance oracle. In some applications (e.g. sports video analysis [19]), given
a curve $\tau\in\mathbb{X}_{m}^{d}$ and an integer $k\geq 2$, one wants to
construct a _distance oracle_ so that for any curve
$\sigma\in\mathbb{X}_{k}^{d}$, $d_{F}(\sigma,\tau)$ can be determined in
$o(km)$ time.

In $\mathbb{R}^{2}$, De Berg et al. [20] designed a data structure of
$O(m^{2})$ size such that for any _horizontal_ segment $\ell$,
$d_{F}(\ell,\tau)$ can be reported in $O(\log^{2}m)$ time. By increasing the
space to $O(m^{2}\log^{2}m)$, they can also report $d_{F}(\ell,\tau^{\prime})$
in $O(\log^{2}m)$ time for any horizontal segment $\ell$ and any vertex-to-
vertex subcurve $\tau^{\prime}$ of $\tau$.

Gudmundsson et al. [35] generalized the above result in $\mathbb{R}^{2}$. They
developed a data structure of $O(n^{3/2})$ size such that for any horizontal
segment $\ell$ and any subcurve $\tau^{\prime}\subseteq\tau$,
$d_{F}(\ell,\tau^{\prime})$ can be reported in $O(\log^{8}m)$ time, where
$\tau^{\prime}$ are delimited by any two points on $\tau$, not necessarily
vertices. They also presented a data structure of the same size such that for
any horizontal segment $\ell$ and any subcurve $\tau^{\prime}\subseteq\tau$,
the translated copy $\ell^{\prime}$ of $\ell$ that minimizes
$d_{F}(\ell^{\prime},\tau^{\prime})$ can be reported in $O(\log^{32}m)$ time.

Buchin et al. [15, 16] improved the distance oracle in $\mathbb{R}^{2}$
recently in several ways. First, they presented a data structure of $O(m\log
m)$ size such that $d_{F}(\ell,\tau)$ can be reported in $O(\log m)$ time for
any horizontal segment $\ell$. Second, they developed a data structure of
$O(m\log^{2}m)$ size such that for any horizontal segment $\ell$ and any
subcurve $\tau^{\prime}\subseteq\tau$, $d_{F}(\ell,\tau^{\prime})$ can be
reported in $O(\log^{3}m)$ time. Note that $\tau^{\prime}$ are delimited by
any two points on $\tau$, not necessarily vertices. Third, for any parameter
$\kappa\in[m]$, they presented a data structure of
$O(m\kappa^{2+\varepsilon}+m^{2})$ size such that for any segment $\ell$ and
any subcurve $\tau^{\prime}\subseteq\tau$, $d_{F}(\ell,\tau^{\prime})$ can be
reported in $O((m/\kappa)\log^{2}m+\log^{4}m)$ time. Note that there is no
restriction on the orientation of $\ell$. Fourth, they developed a data
structure of $O(m\log^{2}m)$ size such that for any horizontal segment $\ell$
and any subcurve $\tau^{\prime}\subseteq\tau$, the translated copy
$\ell^{\prime}$ of $\ell$ that minimizes $d_{F}(\ell^{\prime},\tau^{\prime})$
can be reported in $O(\log^{12}m)$ time. For arbitrarily oriented query
segments, they presented a data structure of
$O(m\kappa^{3+\varepsilon}+m^{2})$ size for any $\kappa\in[m]$ such that for
any segment $\ell$ and any subcurve $\tau^{\prime}\subseteq\tau$, the
translated copy $\ell^{\prime}$ of $\ell$ that minimizes
$d_{F}(\ell^{\prime},\tau^{\prime})$ can be reported in
$O((m/\kappa)^{4}\log^{8}m+\log^{16}m)$ time. If both scaling and translation
can be applied to the arbitrarily oriented segment, they presented a data
structure of $O(m\kappa^{3+\varepsilon}+m^{2})$ size for any $\kappa\in[m]$
such that for any segment $\ell$ and any subcurve
$\tau^{\prime}\subseteq\tau$, the scaled and translated copy $\ell^{\prime}$
of $\ell$ that minimizes $d_{F}(\ell^{\prime},\tau^{\prime})$ can be reported
in $O((m/\kappa)^{2}\log^{4}m+\log^{8}m)$ time.

In $\mathbb{R}^{2}$, Gudmundsson et al. [33] showed that for any $r>0$ and any
$\sigma\in\mathbb{X}_{k}^{2}$, one can check $d_{F}(\sigma,\tau)\leq r$ in
$O(k\log^{2}m)$ time using $O(m\log m)$ space, provided that the edges in
$\sigma$ and $\tau$ are suitably longer than $r$.

In $\mathbb{R}^{d}$, Driemel and Har-Peled [22] proved that for any segment
$\ell$ and any subcurve $\tau^{\prime}\subseteq\tau$, one can return a
$1+\varepsilon$ approximation of $d_{F}(\ell,\tau^{\prime})$ in
$\tilde{O}(\varepsilon^{-2})$ time using $\tilde{O}(m\varepsilon^{-2d})$
space. For any query curve $\sigma\in\mathbb{X}_{k}^{d}$ and any subcurve
$\tau^{\prime}\subseteq\tau$, they can return an $O(1)$-approximation of
$d_{F}(\sigma,\tau^{\prime})$ in $\tilde{O}(k^{2})$ time using $O(m\log m)$
space. In $\mathbb{R}^{d}$, Gudmundsson et al. [34] showed that, conditioned
on SETH, it is impossible to construct in polynomial time a data structure for
a given $\tau\in\mathbb{X}_{m}^{d}$ such that for any
$\sigma\in\mathbb{X}_{k}^{d}$, a 1.001-approximation of $d_{F}(\sigma,\tau)$
can be returned in $O((km)^{1-\delta})$ time for any $\delta>0$.

###  1.2 Our results

We develop a set of polynomials of constant degrees that characterize
$d_{F}(\sigma,\tau)$ and $\hat{d}_{F}(\sigma,\tau)$ for any
$\sigma\in\mathbb{X}_{k}^{d}$ and any $\tau\in\mathbb{X}_{m}^{d}$. This allows
us to construct an arrangement of zero sets of polynomials such that each cell
of the arrangement encodes the exact solution for the problem in question.

_VC dimension._ We obtain an $O(dk\log(km))$ bound on the VC dimension for the
range space $(\mathbb{X}_{m}^{d},\mathcal{R}_{k,m}^{d})$ and its counterpart
for $\hat{d}_{F}$, improving the previous $O(d^{2}k^{2}\log(dkm))$ bound for
$d_{F}$ and $O(d^{2}k\log(dkm))$ bound for $\hat{d}_{F}$. Our bound is very
close to the $\Omega(dk\log k)$ lower bound [24].

_Curve simplification._ We show that for any $\tau\in\mathbb{X}_{m}^{d}$ and
any $r>0$, the curve $\sigma$ with the minimum size that satisfies
$d_{F}(\sigma,\tau)\leq r$ or $\hat{d}_{F}(\sigma,\tau)\leq r$ can be computed
in $O(km)^{O(dk)}$ time, where $k=|\sigma|$. Given $\tau\in\mathbb{X}_{m}^{d}$
and an integer $k\geq 2$, we can compute in $O(km)^{O(dk)}$ time a curve
$\sigma\in\mathbb{X}_{k}^{d}$ that minimizes $d_{F}(\sigma,\tau)$ or
$\hat{d}_{F}(\sigma,\tau)$. These are the first exact algorithms for $d\geq 3$
when the vertices of $\sigma$ are not restricted. We also obtain an
approximation scheme: given any $\tau\in\mathbb{X}_{m}^{d}$, any $r>0$, and
any $\alpha\in(0,1)$, we can compute $\sigma$ in $O(m/\alpha)^{O(d/\alpha)}$
time such that $d_{F}(\sigma,\tau)\leq r$ or $\hat{d}_{F}(\sigma,\tau)\leq r$,
and $|\sigma|$ is $1+\alpha$ times the minimum possible. Only a bicriteria
approximation scheme was known before that approximates both
$d_{F}(\sigma,\tau)$ and $|\sigma|$ [18].

_Range searching._ Let $T$ be a set of $n$ curves in $\mathbb{X}_{m}^{d}$. Let
$k\geq 2$ be a given integer. We present a data structure of
$O(kmn)^{O(d^{4}k^{2})}$ size such that for any $\sigma\in\mathbb{X}_{k}^{d}$
and any $r>0$, it returns every curve $\tau\in T$ that satisfies
$d_{F}(\sigma,\tau)\leq r$. The query time is $O((dk)^{O(1)}\log(kmn))$ plus
output size. The previous solution works in $\mathbb{R}^{2}$ [1], and the
query radius $r$ needs to be given for preprocessing. For $\hat{d}_{F}$, the
query time remains asymptotically the same, and the space improves to
$O(kmn)^{O(d^{2}k)}$.

_Nearest neighbor and distance oracle._ Let $T$ be a set of $n$ curves in
$\mathbb{X}_{m}^{d}$. Let $k\geq 2$ be an integer. We obtain a nearest
neighbor data structure of $O(kmn)^{\mathrm{poly}(d,k)}$ size such that for
any $\sigma\in\mathbb{X}_{k}^{d}$, its nearest neighbor in $T$ under $d_{F}$
can be reported in $O((dk)^{O(1)}\log(kmn))$ time. Given
$\tau\in\mathbb{X}_{m}^{d}$ and an integer $k\geq 2$, we obtain a distance
oracle of $O(km)^{\mathrm{poly}(d,k)}$ size such that for any
$\sigma\in\mathbb{X}_{k}^{d}$ and any subcurve $\tau^{\prime}\subseteq\tau$,
we can report $d_{F}(\sigma,\tau^{\prime})$ in $O((dk)^{O(1)}\log(km))$ time.
The subcurve $\tau^{\prime}$ are delimited by any two points on $\tau$, not
necessarily vertices. The same results also hold for $\hat{d}_{F}$.

In summary, we obtain improved bounds for the VC dimensions under $d_{F}$ and
$\hat{d}_{F}$—by an order of magnitude in the case of $d_{F}$—that are close
to the known lower bound, and we also obtain exact solutions for the curve
simplification, range searching, nearest neighbor search, and distance oracle
problems. Exact solutions were not known for these problems in
$\mathbb{R}^{d}$ for $d\geq 3$; they were not known for the nearest neighbor
search and distance oracle problems even in $\mathbb{R}^{2}$. When $d$ and $k$
are $O(1)$, our curve simplification algorithms run in polynomial time, and
our data structures for the query problems use polynomial space and answer
queries in logarithmic time. Last but not least, the connection with
arrangements of zero sets of polynomials and algebraic geometry may offer new
perspectives on designing algorithms and proving approximation results.

##  2 Background results on algebraic geometry

We survey several algebraic geometric results that will be useful. 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}:(\text{sign}(\rho_{1}(\nu)),...,\text{sign}(\rho_{s}(\nu)))=S\\}$.
For every $i\in[s]$, $\rho_{i}(\nu)=0$ describes a hypersurface in
$\mathbb{R}^{\omega}$. The hypersurfaces
$\bigl{\\{}\rho_{i}(\nu)=0:i\in[s]\bigr{\\}}$ partition $\mathbb{R}^{\omega}$
into open connected 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}$. One sign
condition vector may induce multiple cells. The cells in
$\mathscr{A}(\mathcal{P})$ represent all sign condition vectors that can be
realized. There are algorithms to construct a point in each cell of
$\mathscr{A}(\mathcal{P})$ and optimize a function over a cell.

######  Theorem 2.1 ([5, 6, 44])

Let $\mathcal{P}$ be a set of $s$ polynomials in $\omega$ variables that have
$O(1)$ degrees.

  1. (i)

The number of cells in $\mathscr{A}(\mathcal{P})$ is $s^{\omega}\cdot
O(1)^{\omega}$.

  2. (ii)

A set $Q$ of points can be computed in $s^{\omega+1}\cdot O(1)^{O(\omega)}$
time that contains at least one point in each cell of
$\mathscr{A}(\mathcal{P})$. The sign condition vectors at these points are
computed within the same time bound.

  3. (iii)

For a semialgebraic set $\mathcal{S}$ described using $\mathcal{P}$, the
minimum over $\mathcal{S}$ of a polynomial in the same variables that have
$O(1)$ degree can be computed in $s^{2\omega+1}\cdot O(1)^{O(\omega)}$ time.
The point at the minimum is also returned.

We will need a _point location_ structure for $\mathscr{A}(\mathcal{P})$ so
that for any query point $\nu\in\mathbb{R}^{\omega}$, the cell in
$\mathscr{A}(\mathcal{P})$ that contains $\nu$ can be reported quickly. The
point enclosure data structure proposed by Agarwal et al. [2] is applicable;
however, the query time has a hidden factor that is exponential in $\omega$.
This is acceptable if $\omega$ is $O(1)$, but this may not be so in our case.
Instead, we linearize the zero sets of the polynomials to hyperplanes in
higher dimensions and use the point location solution by Ezra et al. [30].

######  Theorem 2.2 ([30])

Let $\mathcal{P}$ 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 that can locate any query point in $\mathscr{A}(\mathcal{P})$ in
$O(\omega^{3}\log s)$ time.

The next result, which follows from the quantifier elimination result quoted
in [2, Proposition 2.6.2], gives the nature and complexity of an orthogonal
projection of a semialgebraic set.

###### Lemma 2.1

Let $S$ be a semialgebraic set in $\mathbb{R}^{\omega}$ represented by $s$
polynomial inequalities and equalities in $\omega$ variables, each of degree
at most $t$. The orthogonal projection of $S$ in $\mathbb{R}^{\omega-1}$ along
one of the axes is a semialgebraic set of $s^{2\omega}t^{O(\omega)}$
polynomial inequalities and equalities of degrees at most $t^{O(1)}$. The
orthogonal projection can be computed in $s^{2\omega}t^{O(\omega)}$ time.

##  3 Characterizing Fréchet distance with polynomials

Afshani and Driemel [1] developed the following predicates that involve
$\sigma=(w_{1},\ldots,w_{k})\in\mathbb{X}_{k}^{d}$,
$\tau=(v_{1},\ldots,v_{m})\in\mathbb{X}_{m}^{d}$, and $r\in\mathbb{R}_{\geq
0}$. We treat $\tau$ as fixed and both $\sigma$ and $r$ as unknowns. So the
coordinates of each $w_{j}$ are variables. For any segment $\ell$, let
$\mathrm{aff}(\ell)$ denote the support line of $\ell$.

  * •

$P_{1}$ returns true if and only if $d(v_{1},w_{1})\leq r$.

  * •

$P_{2}$ returns true if and only if $d(v_{m},w_{k})\leq r$.

  * •

$P_{3}(i,j)$ returns true if and only if $d(w_{j},v_{i}v_{i+1})\leq r$.

  * •

$P_{4}(i,j)$ returns true if and only if $d(v_{i},w_{j}w_{j+1})\leq r$.

  * •

$P_{5}(i,j,j^{\prime})$ returns true if and only if there exist two points
$p,q\in\mathrm{aff}(v_{i}v_{i+1})$ such that $d(p,w_{j})\leq r$,
$d(q,w_{j^{\prime}})\leq r$, and either $p=q$ or $\overrightarrow{pq}$ and
$\overrightarrow{v_{i}v_{i+1}}$ have the same direction.333The degenerate
possibility of $p=q$ was not included in [1].

  * •

$P_{6}(i,i^{\prime},j)$ returns true if and only if there exist two points
$p,q\in\mathrm{aff}(w_{j}w_{j+1})$ such that $d(p,v_{i})\leq r$,
$d(q,v_{i^{\prime}})\leq r$, and either $p=q$ or $\overrightarrow{pq}$ and
$\overrightarrow{w_{j}w_{j+1}}$ have the same direction.11footnotemark: 1

######  Lemma 3.1 ([1, 24])

It takes $O(km(k+m))$ time to decide whether $d_{F}(\sigma,\tau)\leq r$ from
the truth values of $P_{1}$, $P_{2}$, $P_{3}(i,j)$ and $P_{4}(i,j)$ for all
$i\in[m]$ and $j\in[k]$, $P_{5}(i,j,j^{\prime})$ for all $i\in[m]$,
$j\in[k-1]$, and $j^{\prime}\in[j+1,k]$, and $P_{6}(i,i^{\prime},j)$ for all
$i\in[m-1]$, $i^{\prime}\in[i+1,m]$, and $j\in[k]$. It takes $O(km)$ time to
decide whether $\hat{d}_{F}(\sigma,\tau)\leq r$ from the truth values of
$P_{1}$, $P_{2}$, $P_{3}(i,j)$ and $P_{4}(i,j)$ for all $i\in[m]$ and
$j\in[k]$. No additional knowledge of $\sigma$ or $\tau$ besides the truth
values of these predicates is necessary.

We construct a set of polynomials such that their signs encode the truth
values of the above predicates. The first three polynomials $f_{0}$, $f_{1}$,
and $f_{2}$ are straightforward:

$f_{0}(r)=r\geq 0.$ $P_{1}\,\,\text{returns true}\,\iff
f_{1}(v_{1},w_{1},r)=\|v_{1}-w_{1}\|^{2}-r^{2}\leq 0.$ $P_{2}\,\,\text{returns
true}\,\iff f_{2}(v_{m},w_{k},r)=\|v_{m}-w_{k}\|^{2}-r^{2}\leq 0.$

In the following, we assume that $f_{0}(r)\geq 0$, $f_{1}(v_{1},w_{1},r)\leq
0$, and $f_{2}(v_{m},w_{k},r)\leq 0$.

$P_{3}(i,j)$. We use several polynomials to encode $P_{3}(i,j)$. Let
$\langle\nu,\nu^{\prime}\rangle$ denote the inner product of vectors $\nu$ and
$\nu^{\prime}$. First, observe that
$d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}\cdot\lVert v_{i}-v_{i+1}\rVert^{2}$ can
be written as a polynomial of degree 2 in the coordinates of $w_{j}$.

$d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}\cdot\lVert
v_{i}-v_{i+1}\rVert^{2}=\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_{3,1}(v_{i},v_{i+1},w_{j},r)$ compares the distance
$d(w_{j},\text{aff}(v_{i}v_{i+1}))$ with $r$. It has degree 2. For ease of
presentation, we shorten the notation $f_{3,1}(v_{i},v_{i+1},w_{j},r)$ to
$f_{3,1}^{i,j}$.

$\displaystyle f_{3,1}^{i,j}$
$\displaystyle=\bigl{(}d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}-r^{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}-r^{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 r$ if and only if $f_{3,1}^{i,j}\leq
0$. Therefore, if $f_{3,1}^{i,j}>0$, then $P_{3}(i,j)$ is false. If
$f_{3,1}^{i,j}\leq 0$, we use the following two degree-1 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_{3,2}^{i,j}=\langle w_{j}-v_{i},v_{i+1}-v_{i}\rangle,\quad
f_{3,3}^{i,j}=\langle w_{j}-v_{i+1},v_{i}-v_{i+1}\rangle.$

Specifically, 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_{3,2}^{i,j}\geq 0$ and $f_{3,3}^{i,j}\geq 0$.
As a result, if $f_{3,1}^{i,j}\leq 0$, $f_{3,2}^{i,j}\geq 0$, and
$f_{3,3}^{i,j}\geq 0$, then $P_{3}(i,j)$ is true. The remaining cases are
either $f_{3,2}^{i,j}<0$ or $f_{3,3}^{i,j}<0$. We use the following
polynomials to compare $d(w_{j},v_{i})$ and $d(w_{j},v_{i+1})$ with $r$.

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

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

$P_{4}(i,j)$. We can define polynomials $f_{4,1}^{i,j}$, $f_{4,2}^{i,j}$,
$f_{4,3}^{i,j}$, $f_{4,4}^{i,j}$, and $f_{4,5}^{i,j}$ to encode $P_{4}(i,j)$
in a way analogous to the encoding of $P_{3}(i,j)$. The differences are that
$f_{4,1}^{i,j}$ has degree 4, and $f_{4,2}^{i,j}$ and $f_{4,3}^{i,j}$ have
degree 2.

$P_{5}(i,j,j^{\prime})$. We first check whether $f_{3,1}^{i,j}\leq 0$ and
$f_{3,1}^{i,j^{\prime}}\leq 0$ to make sure that
$d(w_{j},\mathrm{aff}(v_{i}v_{i+1}))\leq r$ and
$d(w_{j^{\prime}},\mathrm{aff}(v_{i}v_{i+1}))\leq r$. If $f_{3,1}^{i,j}>0$ or
$f_{3,1}^{i,j^{\prime}}>0$, then $P_{5}(i,j,j^{\prime})$ is false. Suppose
that $f_{3,1}^{i,j}\leq 0$ and $f_{3,1}^{i,j^{\prime}}\leq 0$. We use the
polynomial $f_{5,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})$
are consistent with the direction of $\overrightarrow{v_{i}v_{i+1}}$.

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

If $f_{5,1}^{i,j,j^{\prime}}\geq 0$, then $P_{5}(i,j,j^{\prime})$ can be
satisfied by taking the projections of $w_{j}$ and $w_{j^{\prime}}$ in
$\mathrm{aff}(v_{i}v_{i+1})$ as the points $p$ and $q$, respectively, in the
definition of $P_{5}(i,j,j^{\prime})$.

Suppose that $f_{5,1}^{i,j,j^{\prime}}<0$. Let $B_{r}$ denote the ball
centered at the origin with radius $r$. Let $\oplus$ denote the Minkowski sum
operator. We claim that $P_{5}(i,j,j^{\prime})$ is true if and only if
$w_{j^{\prime}}\oplus B_{r}\cap w_{j}\oplus
B_{r}\cap\text{aff}(v_{i}v_{i+1})\not=\emptyset$. The reason is as follows.
Since $f_{5,1}^{i,j,j^{\prime}}<0$, the order of the projections of
$w_{j^{\prime}}$ and $w_{j}$ in $\mathrm{aff}(v_{i}v_{i+1})$ are opposite to
the direction of $\overrightarrow{v_{i}v_{i+1}}$. If $w_{j^{\prime}}\oplus
B_{r}\cap w_{j}\oplus B_{r}\cap\text{aff}(v_{i}v_{i+1})\not=\emptyset$, we can
satisfy $P_{5}(i,j,j^{\prime})$ by picking a point in this intersection to be
both $p$ and $q$ in the definition of $P_{5}(i,j,j^{\prime})$. Conversely, if
$w_{j^{\prime}}\oplus B_{r}\cap w_{j}\oplus
B_{r}\cap\text{aff}(v_{i}v_{i+1})=\emptyset$, then for any $p\in w_{j}\oplus
B_{r}\cap\mathrm{aff}(v_{i}v_{i+1})$ and any $q\in w_{j^{\prime}}\oplus
B_{r}\cap\mathrm{aff}(v_{i}v_{i+1})$, the direction of $\overrightarrow{pq}$
is opposite to that of $\overrightarrow{v_{i}v_{i+1}}$, which makes
$P_{5}(i,j,j^{\prime})$ false. We use the degree-2 polynomial
$f_{5,2}^{i,j,j^{\prime}}$ below to capture the ideas above.

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

Specifically, $d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}+\langle
w_{j}-w_{j^{\prime}},v_{i}-v_{i+1}\rangle^{2}\cdot\|v_{i}-v_{i+1}\|^{-2}$ is
equal to the squared distance between $w_{j^{\prime}}$ and the projection of
$w_{j}$ in $\mathrm{aff}(v_{i}v_{i+1})$. Thus, $f_{5,2}^{i,j,j^{\prime}}\leq
0$ if and only if $w_{j^{\prime}}$ is at distance at most $r$ from the
projection of $w_{j}$ in $\mathrm{aff}(v_{i}v_{i+1})$. Because
$d(w_{j},\mathrm{aff}(v_{i}v_{i+1}))\leq r$, if $f_{5,2}^{i,j,j^{\prime}}\leq
0$, we can set both $p$ and $q$ to be the projection of $w_{j}$ in
$\mathrm{aff}(v_{i}v_{i+1})$ to satisfy $P_{5}(i,j,j^{\prime})$.

The remaining case is that $f_{5,2}^{i,j,j^{\prime}}>0$. It means that
$w_{j^{\prime}}$ is at distance more than $r$ from the projection of $w_{j}$
in $\text{aff}(v_{i}v_{i+1})$. Let $p^{*}$ be the point in
$w_{j^{\prime}}\oplus B_{r}\cap\mathrm{aff}(v_{i}v_{i+1})$ closest to $w_{j}$.
In this case, $p^{*}$ lies between the projections of $w_{j^{\prime}}$ and
$w_{j}$ in $\mathrm{aff}(v_{i}v_{i+1})$, so $P_{5}(i,j,j^{\prime})$ is
satisfied if and only if $d(w_{j},p^{*})\leq r$. The distance between $p^{*}$
and the projection of $w_{j}$ in $\mathrm{aff}(v_{i}v_{i+1})$ is equal to

$\frac{\langle w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle}{\lVert
v_{i}-v_{i+1}\rVert}-\sqrt{r^{2}-d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}}.$

$P_{5}(i,j,j^{\prime})$ is satisfied if and only if
$d(w_{j},p^{*})^{2}-r^{2}\leq 0$

$\displaystyle\iff$ $\displaystyle
d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}+\left(\frac{\langle
w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle}{\lVert
v_{i}-v_{i+1}\rVert}-\sqrt{r^{2}-d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}}\right)^{2}-r^{2}\leq
0$ $\displaystyle\iff$
$\displaystyle\left(d(w_{j},\text{aff}(v_{i}v_{i+1}))^{2}-r^{2}\right)\cdot\|v_{i}-v_{i+1}\|^{2}+$
$\displaystyle\left(\langle
w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle-\|v_{i}-v_{i+1}\|\cdot\sqrt{r^{2}-d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}}\right)^{2}\leq
0$ $\displaystyle\iff$ $\displaystyle f_{3,1}^{i,j}+\langle
w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle^{2}-$ $\displaystyle 2\langle
w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle\cdot\|v_{i}-v_{i+1}\|\cdot\sqrt{r^{2}-d(w_{j^{\prime}},\text{aff}(v_{i}v_{i+1}))^{2}}-f_{3,1}^{i,j^{\prime}}\leq
0.$

We move the term containing the square root to the right hand side:

(3.1) $\displaystyle f_{3,1}^{i,j}+\langle
w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle^{2}-f_{3,1}^{i,j^{\prime}}\leq
2\langle
w_{j^{\prime}}-w_{j},v_{i}-v_{i+1}\rangle\cdot\sqrt{-f_{3,1}^{i,j^{\prime}}}$
$\displaystyle\iff$ $\displaystyle
f_{3,1}^{i,j}+\left(f_{5,1}^{i,j,j^{\prime}}\right)^{2}-f_{3,1}^{i,j^{\prime}}\leq-2f_{5,1}^{i,j,j^{\prime}}\sqrt{-f_{3,1}^{i,j^{\prime}}}.$

Recall that we are considering the case of $f_{3,1}^{i,j^{\prime}}\leq 0$ and
$f_{5,1}^{i,j,j^{\prime}}<0$. Therefore, the right hand side of (3.1) is non-
negative. Define the following two polynomials:

$\displaystyle f_{5,3}^{i,j,j^{\prime}}$
$\displaystyle=f_{3,1}^{i,j}+\left(f_{5,1}^{i,j,j^{\prime}}\right)^{2}-f_{3,1}^{i,j^{\prime}},$
$\displaystyle f_{5,4}^{i,j,j^{\prime}}$
$\displaystyle=\left(f_{5,3}^{i,j,j^{\prime}}\right)^{2}+4\left(f_{5,1}^{i,j,j^{\prime}}\right)^{2}f_{3,1}^{i,j^{\prime}}.$

Note that $f_{5,3}^{i,j,j^{\prime}}$ is the left hand side of (3.1), and
$f_{5,4}^{i,j,j^{\prime}}$ is obtained by squaring and rearranging the two
sides of (3.1). Hence, in the case of $f_{3,1}^{i,j^{\prime}}\leq 0$ and
$f_{5,1}^{i,j,j^{\prime}}<0$, $P_{5}(i,j,j^{\prime})$ is true if and only if
(3.1) is satisfied, which is equivalent to either
$f_{5,3}^{i,j,j^{\prime}}\leq 0$ or $f_{5,4}^{i,j,j^{\prime}}\leq 0$.

$P_{6}(i,i^{\prime},j)$. We define polynomials
$f_{6,1}^{i,i^{\prime}\\!\\!,j}$, $f_{6,2}^{i,i^{\prime}\\!\\!,j}$,
$f_{6,3}^{i,i^{\prime}\\!\\!,j}$, and $f_{6,4}^{i,i^{\prime}\\!\\!,j}$ to
encode $P_{6}(i,i^{\prime},j)$ in a way analogous to the encoding of
$P_{5}(i,j,j^{\prime})$. The polynomial $f_{6,4}^{i,i^{\prime}\\!\\!,j}$
involves $(f_{4,1}^{i,j})^{2}$ and $(f_{4,1}^{i^{\prime}\\!\\!,j})^{2}$. So
$f_{6,4}^{i,i^{\prime}\\!\\!,j}$ has degree 8.

Let $\widehat{\mathcal{P}}$ be the set of polynomials including $f_{0}$ and
those for $P_{1}$, $P_{2}$, $P_{3}(i,j)$’s, and $P_{4}(i,j)$’s. Let
$\mathcal{P}$ be union of $\widehat{\mathcal{P}}$ and the polynomials for
$P_{5}(i,j,j^{\prime})$’s and $P_{6}(i,i^{\prime},j)$’s. By Lemma 3.1, we get:

###### Corollary 3.1

Given the corresponding sign condition vector of $\mathcal{P}$ for $\sigma$
and $r$, we can check whether $d_{F}(\sigma,\tau)\leq r$ in $O(km(k+m))$ time.
Given the corresponding sign condition vector of $\widehat{\mathcal{P}}$ for
$\sigma$ and $r$, we can check whether $\hat{d}_{F}(\sigma,\tau)\leq r$ in
$O(km)$ time.

##  4 Applications.

###  4.1 VC dimension.

We bound the VC dimension of the range space
$(\mathbb{X}_{m}^{d},\mathcal{R}_{k,m}^{d})$ induced by $d_{F}$. Let
$T=\\{\tau_{1},\ldots,\tau_{n}\\}$ be a set of $n$ curves in
$\mathbb{X}_{m}^{d}$. For $a\in[n]$, we denote the vertices of $\tau_{a}$ by
$(v_{a,1},v_{a,2},\ldots,v_{a,m})$. Let $\sigma=(w_{1},\ldots,w_{k})$ be an
unknown curve in $\mathbb{X}_{k}^{d}$. Let $r$ be an unknown positive real
number.

For $a\in[n]$, let $\mathcal{P}_{a}$ be the set of polynomials for $\tau_{a}$,
$\sigma$, and $r$ as described in Section 3. The zero set of every polynomial
in $\mathcal{P}_{a}$ is a hypersurface in $\mathbb{R}^{dk+1}$. The cells of
the arrangement $\mathscr{A}(\mathcal{P}_{a})$ in the halfspace $r\geq 0$
capture all possible sign condition vectors for $\mathcal{P}_{a}$. By
Corollary 3.1, for each cell of $\mathscr{A}(\mathcal{P}_{a})$ in the
halfspace $r\geq 0$, the inequality $d_{F}(\sigma,\tau_{a})\leq r$ either
holds for all points in that cell or fails for all points in that cell.

Let $\mathcal{P}=\bigcup_{a=1}^{n}\mathcal{P}_{a}$. It follows that for every
curve $\sigma=(w_{1},\ldots,w_{k})\in\mathbb{X}_{k}^{d}$ and every $r\geq 0$,
the cell in $\mathscr{A}(\mathcal{P})$ that contains the point
$(w_{1},\ldots,w_{k},r)$ represents the subset of curves in $T$ that are at
Fréchet distances at most $r$ from $\sigma$. So the cardinality of
$\mathcal{R}_{k,m}^{d}|_{T}=\\{R\cap T:R\in\mathcal{R}_{k,m}^{d}\\}$ is at
most the number of cells in $\mathscr{A}(\mathcal{P})$ which is
$O(nkm^{2})^{dk+1}$ by Theorem 2.1(i). The VC dimension is the cardinality of
the largest $T$ such that $\mathcal{R}_{k,m}^{d}|_{T}$ contains all possible
subsets of $T$. Hence, if $\Delta$ denotes the VC dimension, then
$2^{\Delta}\leq O(\Delta km^{2})^{dk+1}$, which implies that
$\Delta=O(dk\log(km)+dk\log\Delta)$ and hence $\Delta=O(dk\log(km))$. The same
bound also works for $\hat{d}_{F}$.

###### Theorem 4.1

The VC dimensions of $(\mathbb{X}_{m}^{d},\mathcal{R}_{k,m}^{d})$ and its
counterpart for $\hat{d}_{F}$ are $O(dk\log(km))$.

###  4.2 Curve simplification.

Let $\tau\in\mathbb{X}_{m}^{d}$ be the input curve. The first problem is that
given $r>0$, compute a curve $\sigma$ with the minimum size such that
$d_{F}(\sigma,\tau)\leq r$. We enumerate $b$ from 2 to $m$ until we can find a
curve $\sigma=(w_{1},\ldots,w_{b})\in\mathbb{X}_{b}^{d}$ such that
$d_{F}(\sigma,\tau)\leq r$. When this happens, we obtain the desired curve of
the minimum size. For a particular $b$, we construct the set $\mathcal{P}$ of
polynomials in Section 3 for $\tau$ and $\sigma$. Note that $r$ is not a
variable because it is specified in the input. By Theorem 2.1(ii), we can
compute in $O(bm^{2})^{db+1}\cdot O(1)^{O(db)}$ time a set $Q$ of points such
that $Q$ contains at least one point in each cell of
$\mathscr{A}(\mathcal{P})$, as well as the sign condition vectors for
$\mathcal{P}$ at the points in $Q$. By Corollary 3.1, it takes another
$O(bm^{2})$ time per cell to determine whether the inequality
$d_{F}(\sigma,\tau)\leq r$ is satisfied by the point(s) of $Q$ in that cell.
If the answer is yes for some cell in $\mathscr{A}(\mathcal{P})$, we stop; any
point in $Q$ in that cell gives the desired curve $\sigma$. If the answer is
no for every cell in $\mathscr{A}(\mathcal{P})$, we increment $b$ and repeat
the above. Let $k$ be the minimum size of $\sigma$. The total running time is
$O(km)^{O(dk)}$.

The second problem is that given an integer $k\geq 2$, compute a curve
$\sigma\in\mathbb{X}_{k}^{d}$ that minimizes $d_{F}(\sigma,\tau)$. We
construct the same set $\mathcal{P}$ of polynomials as in the previous
paragraph; however, $r$ is a variable in this case. By Theorem 2.1(ii) and as
discussed in the previous paragraph, we can determine in $O(km)^{O(dk)}$ time
the subset $\mathcal{K}$ of cells of $\mathscr{A}(\mathcal{P})$ that satisfy
the inequality $d_{F}(\sigma,\tau)\leq r$. Specifically, we obtain a set $Q$
of points such that every point in $Q$ lies in a cell of $\mathcal{K}$, and
every cell in $\mathcal{K}$ contains a point in $Q$, and we also obtain the
sign condition vectors at the points in $Q$ which give the polynomial
inequalities and equalities that describe every cell in $\mathcal{K}$. This
yields a collection of semialgebraic sets. We invoke Theorem 2.1(iii) to
determine in $O(km)^{O(dk)}$ time the minimum $r$ attained in each such
semialgebraic set. The minimum over all such sets is the minimum
$d_{F}(\sigma,\tau)$ desired. The total running time is $O(km)^{O(dk)}$.

The third problem is that given $\alpha\in(0,1)$ and $r>0$, compute a curve
$\sigma$ of size within a factor $1+\alpha$ of the minimum possible such that
$d_{F}(\sigma,\tau)\leq r$. We proceed in a greedy fashion as in the
bicriteria approximation scheme in [18] as follows. Let
$\tau[v_{b},v_{b^{\prime}}]$ denote the subcurve of $\tau$ from $v_{b}$ to
$v_{b^{\prime}}$. We enumerate $i=1,2,\ldots$ until the largest value such
that $\tau[v_{1},v_{i}]$ can be simplified to a curve $\sigma_{1}$ of $\lceil
1/\alpha\rceil$ vertices such that $d_{F}(\sigma_{1},\tau[v_{1},v_{i}])\leq
r$. This takes $i\cdot O(m/\alpha)^{O(d/\alpha)}$ time as discussed in our
solution for the first problem. We repeat this procedure on the suffix
$\tau[v_{i+1},v_{m}]$ to approximate the longest prefix of
$\tau[v_{i+1},v_{m}]$ by another curve $\sigma_{2}$ of $\lceil 1/\alpha\rceil$
vertices. In this way, we get a sequence of curves
$\sigma_{1},\sigma_{2},...$. We connect them in this order to form a curve
$\sigma$. Given that the last vertex of $\sigma_{1}$ is at a distance no more
than $r$ to $v_{i}$ and the first vertex of $\sigma_{2}$ is at a distance no
more than $r$ to $v_{i+1}$, linear interpolation guarantees that the
connection between $\sigma_{1}$ and $\sigma_{2}$ does not violate the Fréchet
distance bound of $r$. The same analysis can be applied to all the other
connections. Since we only introduce one extra vertex for every $1/\alpha$
edges in the optimal simplification, the size of $\sigma$ is at most
$(1+\alpha)$ times the minimum possible. The total running time is $m\cdot
O(m/\alpha)^{O(d/\alpha)}=O(m/\alpha)^{O(d/\alpha)}$.

The above results also hold for $\hat{d}_{F}$.

###### Theorem 4.2

Let $\tau$ be a curve in $\mathbb{X}_{m}^{d}$. For every $r>0$, we can compute
in $O(km)^{O(dk)}$ time the curve $\sigma$ of the minimum size $k$ that
satisfies $d_{F}(\sigma,\tau)\leq r$. For every integer $k\geq 2$, we can
compute in $O(km)^{O(dk)}$ time the curve $\sigma\in\mathbb{X}_{k}^{d}$ that
minimizes $d_{F}(\sigma,\tau)$. For every $\alpha\in(0,1)$ and every $r>0$, we
can compute in $O(m/\alpha)^{O(d/\alpha)}$ time a curve $\sigma$ of size
$1+\alpha$ times the minimum possible such that $d_{F}(\sigma,\tau)\leq r$.
These results also hold for $\hat{d}_{F}$.

###  4.3 Range searching.

Let $T=\\{\tau_{1},\ldots,\tau_{n}\\}$ be $n$ curves in $\mathbb{X}_{m}^{d}$.
Let $k\geq 2$ be a given integer. We want to construct a data structure such
that for any query curve $\sigma=(w_{1},\ldots,w_{k})\in\mathbb{X}_{k}^{d}$
and any $r>0$, we can report the subset of $T$ that are within a Fréchet
distance $r$ from $\sigma$. Let $\mathcal{P}$ be the set of $O(km^{2}n)$
polynomials that we introduce for bounding the VC dimension under $d_{F}$.

As discussed in Section 4.1, every cell in $\mathscr{A}(\mathcal{P})$
represents a subset $T^{\prime}\subseteq T$ such that for every $\tau_{a}\in
T^{\prime}$ and every point $(w_{1},\ldots,w_{k},r)$ in that cell,
$d_{F}((w_{1},\ldots,w_{k}),\tau_{a})\leq r$. Conceptually speaking, it
suffices to perform a point location in $\mathscr{A}(\mathcal{P})$ using the
query point $(w_{1},\ldots,w_{k},r)$. This can be accomplished using a tree
that represents a hierarchical decomposition; each node stores a small subset
of the polynomials so that we can compare the query point with the arrangement
of this small subset to decide which child to visit. For example, the point
enclosure data structure in [2] is organized like this. Unfortunately, the
arrangement of this small subset of polynomials at each node has size
exponential in the ambient space dimension. In our case, this dimension is
$dk+1$, so querying takes time exponential in $dk+1$ at each node which is
undesirable.

Fortunately, as stated in Theorem 2.2, point location in an arrangement of
hyperplanes has a much better dependence on the ambient space dimension. We
linearize the zero sets of the polynomials in $\mathcal{P}$, that is, we
introduce a new variable to stand for every product of monomials of variables.
Since each polynomial in $\mathcal{P}$ has degree at most 8 and involves at
most two vertices of $\sigma$, after linearization, the total number of
variables cannot be more than $O(d^{8}k^{2})$. In fact, a careful examination
of the terms of these polynomials show that there are no more than
$O(d^{4}k^{2})$ variables after linearization. Hence, we have a set of
$O(km^{2}n)$ hyperplanes in $O(d^{4}k^{2})$ dimensions. Building the point
location data structure in Theorem 2.2 for this arrangement of hyperplanes
solves our problem.

###### Theorem 4.3

Let $T=\\{\tau_{1},\ldots,\tau_{n}\\}$ be a set of $n$ curves in
$\mathbb{X}_{m}^{d}$. Let $k\geq 2$ be a given integer. We can construct a
data structure of $O(kmn)^{O(d^{4}k^{2}\log(dk))}$ size in
$O(kmn)^{O(d^{4}k^{2}\log(dk))}$ expected time such that for any query curve
$\sigma\in\mathbb{X}_{k}^{d}$ and any $r>0$, the subset of $T$ that are within
a Fréchet distance of $r$ from $\sigma$ can be reported in time
$O((dk)^{O(1)}\log(kmn))$ plus the output size.

For $\hat{d}_{F}$, the exponents in the space and preprocessing time in
Theorem 4.3 improve to $O(d^{2}k\log(dk))$ because we only need to linearize
the zero sets of the polynomials for $P_{1}$, $P_{2}$, $P_{3}(i,j)$, and
$P_{4}(i,j)$.

###  4.4 Nearest neighbor and distance oracle.

We first examine the nearest neighbor query. Let
$T=\\{\tau_{1},\ldots,\tau_{n}\\}$ be $n$ curves in $\mathbb{X}_{m}^{d}$. Let
$k\geq 2$ be a given integer. We construct the set of polynomials
$\mathcal{P}$ for $T$ as in Section 4.3 for range searching. The variables are
$r$ and the coordinates of the vertices of $\sigma=(w_{1},\ldots,w_{k})$. So
we are in $\mathbb{R}^{dk+1}$. Without loss of generality, let the $r$-axis be
the vertical axis.

Let $\mathcal{K}$ be the subset of cells in $\mathscr{A}(\mathcal{P})$ that
represent non-empty range searching results. Let $\bigcup\mathcal{K}$ denote
the union of cells in $\mathcal{K}$. Observe that $\bigcup\mathcal{K}$ is
_upward monotone_ in the sense that its intersection with any vertical line is
either empty or a halfline that extends vertically upward. It is because if
$(\sigma,r)\in\bigcup\mathcal{K}$, there is a non-empty subset
$T^{\prime}\subseteq T$ such that all curves in $T^{\prime}$ are within a
Fréchet distance of $r$ from $\sigma$; therefore, for any $r^{\prime}>r$, all
curves in $T^{\prime}$ are also within a Fréchet distance of $r^{\prime}$ from
$\sigma$. The upward monotonicity of $\bigcup\mathcal{K}$ allows us to show
the next result.

###### Lemma 4.1

The lower boundary of $\bigcup\mathcal{K}$ is $\bigcup\mathcal{L}$ for some
subset $\mathcal{L}\subseteq\mathcal{K}$. Moreover, $\mathcal{L}$ can be
constructed in $O(kmn)^{O(dk)}$ time.

  * Proof.

It suffices to prove that a cell $C\in\mathcal{K}$ cannot lie partially in the
lower boundary of $\bigcup\mathcal{K}$. Assume to the contrary that a portion
of $C$ lies in the lower boundary of $\bigcup\mathcal{K}$, but a portion of
$C$ does not. It follows that there is a point $p$ in the interior of $C$ such
that $p$ lies in the lower boundary of $\bigcup\mathcal{K}$, but any
arbitrarily small open neighborhood of $p$ in $C$ contains a point of $C$ that
does not lie in the lower boundary of $\bigcup\mathcal{K}$. Shoot a ray
$\gamma$ vertical downward from $p$. If $\gamma$ intersects another cell in
$\mathcal{K}$, then $p$ cannot lie in the lower boundary of
$\bigcup\mathcal{K}$, a contradiction. Suppose that $\gamma$ does not
intersect another cell in $\mathcal{K}$. Then, there must exist some open
neighborhood $N_{p}$ of $p$ in $C$ such that one can shoot vertical rays
downward from points in $N_{p}$ without intersecting another cell in
$\mathcal{K}$. But then $N_{p}$ must be part of the lower boundary of
$\bigcup\mathcal{K}$, a contradiction to what we said earlier about
arbitrarily small open neighborhoods of $p$ in $C$. This completes the proof
of the first part of the lemma.

We construct $\mathcal{L}$ as follows. First, by Theorem 2.1(ii), we spend
$O(kmn)^{O(dk)}$ time to construct a set $Q$ of points that contain points in
each cell in $\mathscr{A}(\mathcal{P})$. The sign condition vectors at the
points in $Q$ are also computed. Note that the cardinality of $Q$ is
$O(kmn)^{O(dk)}$. For every cell in $\mathscr{A}(\mathcal{P})$, a point in
$Q\cap C$ represents a curve $\sigma$ and a value $r$; we check whether
$d_{F}(\sigma,\tau_{a})\leq r$ for all $a\in[n]$ in $O(kmn\log(km))$ time,
which tells us whether $C\in\mathcal{K}$. For every cell $C\in\mathcal{K}$, we
shoot a vertical ray downward from a point $p\in Q\cap C$ to see if the ray
intersects another cell in $\mathcal{K}$. This check is done as follows. Take
any other cell $C^{\prime}\in\mathcal{K}$. The sign condition vector of a
point in $Q\cap C^{\prime}$ gives the polynomial inequalities and equalities
that describe $C^{\prime}$. Let $p=(w_{1},\ldots,w_{k},r_{0})$. Plug
$w_{1},\ldots,w_{k}$ into the polynomials in the description of $C^{\prime}$.
Note that the polynomials are independent of $r$, or quadratic in $r$, or
biquadratic in $r$. In $O(dkm^{2}n)$ time, we can solve for the conditions on
$r$ imposed by the polynomials in the description of $C^{\prime}$. In general,
each polynomial equality/inequality specify $O(1)$ disjoint ranges of $r$ for
which the polynomial equality/inequality is satisfied. Starting with the range
$r<r_{0}$ imposed by $p$, we can examine each polynomial in turn to
“accumulate” the disjoint ranges of $r$. That is, if $\mathcal{R}$ is the
current list of disjoint ranges of $r$, then for every range $R$ of $r$ given
by the next polynomial equality/inequality, we compute the new ranges
$\\{R\cap R^{\prime}:R^{\prime}\in\mathcal{R}\\}$. The cardinality of
$\mathcal{R}$ increases by $O(1)$ after processing each polynomial
equality/inequality. Hence, we can decide in $\tilde{O}(km^{2}n)$ time whether
the downward ray from $p$ intersects $C^{\prime}$ or not, which means that we
can decide in $O(kmn)^{O(dk)}$ time whether $C$ belongs to $\mathcal{L}$. In
all, we can construct $\mathcal{L}$ in $|\mathcal{L}|\cdot
O(kmn)^{O(dk)}=O(kmn)^{O(dk)}$ time.

We are interested in $\mathcal{L}$ because for any
$\sigma\in\mathbb{X}_{k}^{d}$, if $(\sigma,r)$ belongs to some cell
$C\in\mathcal{L}$, then $C$ must represent some curve $\tau_{a}\in T$ in the
range searching result using $(\sigma,r)$. It follows that $\tau_{a}$ is a
nearest neighbor of $\sigma$. Therefore, we want to perform point location in
the vertical projection of the cells in $\mathcal{L}$ into $\mathbb{R}^{dk}$.
By Lemma 2.1, the polynomials that define the downward projection of
$\mathcal{L}$ have constant degree, and they can be computed in
$|\mathcal{L}|\cdot O(kmn)^{O(dk)}=O(kmn)^{O(dk)}$ time. It follows that there
are $O(kmn)^{O(dk)}$ polynomials that define the projection of $\mathcal{L}$
in $\mathbb{R}^{dk}$. To support point location in the projection of
$\mathcal{L}$, we linearize the zero sets of these polynomials in the
projection to form hyperplanes in $(dk)^{O(1)}$ dimensions. Then, we apply
Theorem 2.2 to these hyperplanes to obtain a point location data structure.
Doing the point location in this arrangement of hyperplanes gives the nearest
neighbor of $\sigma$. In order to report the nearest neighbor distance, each
cell $C$ in the projection of $\mathcal{L}$ corresponds to a cell $\hat{C}$ in
the arrangement of the hyperplanes after linearization, so we store at
$\hat{C}$ one of the polynomial equalities in the definition of the preimage
of $C$ that involves $r$. Then, after the point location, we can solve that
polynomial equality for $r$. Every polynomial is quadratic or biquadratic in
$r$, so it can be solved in $O(d)$ time.

###### Theorem 4.4

Let $T=\\{\tau_{1},\ldots,\tau_{n}\\}$ be $n$ curves in $\mathbb{X}_{m}^{d}$.
Let $k\geq 2$ be a given integer. We can construct a data structure of
$O(kmn)^{\mathrm{poly}(d,k)}$ size in $O(kmn)^{\mathrm{poly}(d,k)}$ expected
time such that for any $\sigma\in\mathbb{X}_{k}^{d}$, we can find its nearest
neighbor in $T$ under $d_{F}$ or $\hat{d}_{F}$ in $O((dk)^{O(1)}\log(kmn))$
time. The nearest neighbor distance is reported within the same time bound.

Theorem 4.4 gives a distance oracle in the special case of $n=1$.

###### Theorem 4.5

Let $\tau$ be a curve in $\mathbb{X}_{m}^{d}$. Let $k\geq 2$ be a given
integer. We can construct a data structure of $O(km)^{\mathrm{poly}(d,k)}$
size in $O(km)^{\mathrm{poly}(d,k)}$ expected time such that for any
$\sigma\in\mathbb{X}_{k}^{d}$, we can return $d_{F}(\sigma,\tau)$ or
$\hat{d}_{F}(\sigma,\tau)$ in $O((dk)^{O(1)}\log(km))$ time.

Next, we discuss how to extend Theorem 4.5 to allow a query to be performed on
a subcurve $\tau^{\prime}\subseteq\tau$. The subcurve $\tau^{\prime}$ can be
delimited in one of two ways. First, $\tau^{\prime}$ can be delimited by two
points that lie on two distinct edges of $\tau$. Second, $\tau^{\prime}$ can
be a subset of some edge of $\tau$.

For the first possibility, we enumerate
$\tau_{i,i^{\prime}}=(v_{i},\ldots,v_{i^{\prime}})$ for all $i\in[m-1]$ and
$i^{\prime}\in[i+1,m]$. We use $\hat{\tau}_{i,i^{\prime}}$ to denote a
subcurve of $\tau$ that is delimited by two points on $v_{i}v_{i+1}$ and
$v_{i^{\prime}-1}v_{i^{\prime}}$. We can represent the endpoints of
$\hat{\tau}_{i,i^{\prime}}$ as $(1-\beta)v_{i}+\beta v_{i+1}$ and
$(1-\gamma)v_{i^{\prime}-1}+\gamma v_{i^{\prime}}$ for some
$\beta,\gamma\in(0,1)$. In the formulation of the polynomials for $P_{1}$,
$P_{2}$, $P_{3}(i,j)$’s, $P_{4}(i,j)$’s, $P_{5}(i,j,j^{\prime})$’s, and
$P_{6}(i,i^{\prime},j)$’s for $\hat{\tau}_{i,i^{\prime}}$, we follow their
formulations for the curve $\tau_{i,i^{\prime}}$ except that every reference
to $v_{i}$ is replaced by $(1-\beta)v_{i}+\beta v_{i+1}$ and every reference
to $v_{i^{\prime}}$ is replaced by $(1-\gamma)v_{i^{\prime}-1}+\gamma
v_{i^{\prime}}$. We also need the polynomials $\beta,1-\beta,\gamma,1-\gamma$
in order to check $\beta,\gamma\in(0,1)$.

For the second possibility, we enumerate $\tau_{i}=(v_{i},v_{i+1})$ for all
$i\in[m-1]$. We use $\hat{\tau}_{i}$ to denote a subcurve of $\tau$ that is
delimited by two points on $v_{i}v_{i+1}$. We can represent the endpoints of
$\hat{\tau}_{i}$ as $(1-\beta)v_{i}+\beta v_{i+1}$ and $(1-\gamma)v_{i}+\gamma
v_{i+1}$ for some $\beta,\gamma\in(0,1)$. In the formulation of the
polynomials for $P_{1}$, $P_{2}$, $P_{3}(i,j)$’s, $P_{4}(i,j)$’s,
$P_{5}(i,j,j^{\prime})$’s, and $P_{6}(i,i^{\prime},j)$’s for $\hat{\tau}_{i}$,
we follow their formulations for $\tau_{i}$ except that every reference to
$v_{i}$ is replaced by $(1-\beta)v_{i}+\beta v_{i+1}$ and every reference to
$v_{i+1}$ by $(1-\gamma)v_{i}+\gamma v_{i+1}$. We also need the polynomials
$\beta,1-\beta,\gamma,1-\gamma,\gamma-\beta$ in order to check
$\beta,\gamma\in(0,1)$ and $\beta<\gamma$.

For every $i\in[m-1]$ and every $i^{\prime}\in[i+1,m]$, we have a set
$\mathcal{P}_{i,i^{\prime}}$ of polynomials constructed for
$\tau_{i,i^{\prime}}$ and another set $\hat{\mathcal{P}}_{i,i^{\prime}}$ of
polynomials constructed for $\hat{\tau}_{i,i^{\prime}}$. For every
$i\in[m-1]$, we also have a set $\hat{\mathcal{P}}_{i}$ of polynomials
constructed for $\hat{\tau}_{i}$. The polynomials in each
$\mathcal{P}_{i,i^{\prime}}$ have $dk+1$ variables, so we apply Theorem 4.5 to
construct a data structure $D_{i,i^{\prime}}$ of
$O((km)^{\mathrm{poly}(d,k)})$ size and $O((dk)^{O(1)}\log(km))$ query time.
The polynomials in each $\hat{\mathcal{P}}_{i,i^{\prime}}$ have
$dk+3=\Theta(dk)$ variables, so we can still construct a data structure
$\hat{D}_{i,i^{\prime}}$ using the techniques used for showing Theorem 4.5.
The data structure $\hat{D}_{i,i^{\prime}}$ also has
$O((km)^{\mathrm{poly}(d,k)})$ size and $O((dk)^{O(1)}\log(km))$ query time.
Similarly, we also construct a data structure $\hat{D}_{i}$ for $\hat{P}_{i}$.

At query time, we are given the query curve $\sigma$ and the subcurve
$\tau^{\prime}\subseteq\tau$. If $\tau^{\prime}=\tau_{i,i^{\prime}}$ for some
$i,i^{\prime}$, we query $D_{i,i^{\prime}}$ using $\sigma$ as we explained in
showing Theorems 4.4 and 4.5. If $\tau^{\prime}=\hat{\tau}_{i,i^{\prime}}$ for
some $i,i^{\prime}$, then $\beta$ and $\gamma$ are also specified. Therefore,
we are also doing a point location using $(\sigma,\beta,\gamma)$ in the
orthogonal projection of $\mathscr{A}(\hat{\mathcal{P}}_{i,i^{\prime}})$ onto
the $\mathbb{R}^{dk+2}$. Therefore, the same query strategy works. If
$\tau^{\prime}=\hat{\tau}_{i}$ for some $i$, we query $\hat{D}_{i}$.

###### Theorem 4.6

Let $\tau$ be a curve in $\mathbb{X}_{m}^{d}$. Let $k\geq 2$ be a given
integer. We can construct a data structure of $O(km)^{\mathrm{poly}(d,k)}$
size in $O(km)^{\mathrm{poly}(d,k)}$ expected time such that for any
$\sigma\in\mathbb{X}_{k}^{d}$ and any subcurve $\tau^{\prime}\subseteq\tau$,
we can return $d_{F}(\sigma,\tau^{\prime})$ or
$\hat{d}_{F}(\sigma,\tau^{\prime})$ in $O((dk)^{O(1)}\log(km))$ time. The
subcurve $\tau^{\prime}$ are delimited by two points on $\tau$, not
necessarily vertices.

##  5 Conclusion.

We demonstrate a connection between (weak) Fréchet distance problems and
algebraic geometry that allows us to obtain improved VC dimension bounds and
exact algorithms for several fundamental problems concerning (weak) Fréchet
distance. When $d$ and $k$ are $O(1)$, our results imply polynomial-time curve
simplification algorithms and data structures for range searching, nearest
neighbor search, and distance determination that have polynomial space
complexities and logarithmic query times. The connection to algebraic geometry
may offer new perspectives in designing new algorithms and proving
approximation results. Our approach is general enough that it should be
possible to to handle other variants of the problems considered.

## References

  * [1] P. Afshani and A. Driemel.  On the complexity of range searching among curves.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 898–917, 2018.
  * [2] P.K. Agarwal, B. Aronov, E. Ezra, and J. Zahl.  Efficient algorithm for generalized polynomial partitioning and its applications.  SIAM Journal on Computing, 50:760–787, 2021.
  * [3] P.K. Agarwal, S. Har-Peled, N.H. Mustafa, and Y. Wang.  Near-linear time approximation algorithms for curve simplification.  Algorithmica, 42(3):203–219, 2005.
  * [4] H. Alt and M. Godau.  Computing the Fréchet distance between two polygonal curves.  International Journal of Computational Geometry and Applications, 5:75–91, 1995.
  * [5] S. Basu, R. Pollack, and M.-F. 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.
  * [6] S. Basu, R. Pollack, and M.-F. Roy.  Algorithms in Real Algebraic Geometry.  Springer, 2007.
  * [7] S. Bereg, M. Jiang, W. Wang, B. Yang, and B. Zhu.  Simplifying 3D polygonal chains under the discrete Fréchet distance.  In Proceedings of the Latin American Symposium on Theoretical Informatics, pages 630–641, 2008.
  * [8] K. Bringmann and B.R. Chaudhury.  Polyline simplification has cubic complexity.  In Proceedings of the International Symposium on Computational Geometry, pages 18:1–18:16, 2019.
  * [9] K. Bringmann, A. Driemel, A. Nusser, and I. Psarros.  Tight bounds for approximate near neighbor searching for time series under Fréchet distance.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 517–550, 2022.
  * [10] Frederik Brüning and Anne Driemel.  Simplified and improved bounds on the VC-dimension for elastic distance measures, 2023.  arXiv:2308.05998.
  * [11] K. Buchin, M. Buchin, D. Duran, B. T. Fasy, R. Jacobs, V. Sacristán, R.I. Silveira, F. Staals, and C. Wenk.  Clustering trajectories for map construction.  In Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 14:1–14:10, 2017\.
  * [12] K. Buchin, M. Buchin, J. Gudmundsson, M. Löffler, and J. Luo.  Detecting commuting patterns by clustering subtrajectories.  International Journal of Computational Geometry & Applications, 21(3):253–282, 2011.
  * [13] K. Buchin, A. Driemel, J. Gudmundsson, M. Horton, I. Kostitsyna, M. Löffler, and M. Struijs.  Approximating $(k,l)$-center clustering for curves.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 2922–2938, 2019.
  * [14] M. Buchin, A. Driemel, and D. Rohde.  Approximating $(k,l)$-median clustering for polygonal curves.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 2697–2717, 2021.
  * [15] M. Buchin, I. van der Hoog, T. Ophelders, L. Schlipf, R. I. Silveira, and F. Staals.  Efficient Fréchet distance queries for segments, 2022.  arXiv:2203.01794.
  * [16] M. Buchin, I. van der Hoog, T. Ophelders, L. Schlipf, R.I. Silveira, and F. Staals.  Efficient Fréchet distance queries for segments.  In Proceedings of the European Symposium on Algorithms, pages 29:1–29:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [17] S.-W. Cheng and H. Huang.  Approximate nearest neighbor for polygonal curves under Fréchet distance.  In Proceedings of the International Colloquium on Automata, Languages and Programming, pages 40:1–40:18, 2023.
  * [18] S.-W. Cheng and H. Huang.  Curve simplification and clustering under Fréchet distance.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 1414–1432, 2023.
  * [19] M. de Berg, A.F. Cook IV, and J. Gudmundsson.  Fast Fréchet queries.  Computational Geometry : Theory and Applications, 46:747–755, 2013\.
  * [20] M. de Berg, A.D. Mehrabi, and T. Ophelders.  Data structures for Fréchet queries in trajectory data.  In Proceedings of the Canadian Conference on Computational Geometry, pages 214–219, 2017.
  * [21] D.H. Douglas and T.K. Peucker.  Algorithms for the reduction of the number of points required to represent a digitized line or its caricature.  Cartographica: The International Journal for Geographic Information and Geovisualization, 10(2):112–122, 1973.
  * [22] A. Driemel and S. Har-Peled.  Jaywalking your dog: computing the Féchet distance with shortcuts.  SIAM Journal on Computing, 42:1830–1866, 2013.
  * [23] A. Driemel, A. Krivošija, and C. Sohler.  Clustering time series under the Fréchet distance.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 766–785, 2016.
  * [24] A. Driemel, A. Nusser, J.M. Phillips, and I. Psarros.  The VC dimension of metric balls under Fréchet and Hausdorff distances.  Discrete & Computational Geometry, 66:1351–1381, 2021.
  * [25] A. Driemel and I. Psarros.  $(2+\epsilon)$-ANN for time series under the Fréchet distance, 2021\.  arXiv:2008.09406v5.
  * [26] A. Driemel and I. Psarros.  ANN for time series under the Fréchet distance.  In Proceedings of the International Algorithms and Data Structures Symposium, pages 315–328, 2021.
  * [27] A. Driemel, I. Psarros, and M. Schmidt.  Sublinear data structures for short Fréchet queries, 2019.  arXiv:1907.04420.
  * [28] A. Driemel and F. Silvestri.  Locality-sensitive hashing of curves.  In Proceedings of the International Symposium on Computational Geometry, pages 37:1–37:16, 2017.
  * [29] I.Z. Emiris and I. Psarros.  Products of Euclidean metrics, applied to proximity problems among curves: Unified treatment of discrete fréchet and dynamic time warping distances.  ACM Transactions on Spatial Algorithms and Systems, 6(4):1–20, 2020\.
  * [30] E. Ezra, S. Har-Peled, H. Kaplan, and M. Sharir.  Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location.  Discrete & Computational Geometry, 64(1):109–173, 2020.
  * [31] A. Filtser, O. Filtser, and M.J. Katz.  Approximate nearest neighbor for curves: simple, efficient, and deterministic.  In Proceedings of the International Colloquium on Automata, Languages, and Programming, pages 48:1–48:19, 2020.
  * [32] M. Godau.  A natural metric for curves - computing the distance for polygonal chains and approximation algorithms.  In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science, pages 127–136, 1991.
  * [33] J. Gudmundsson, M. Mirzanezhad, A. Mohades, and C. Wenk.  Fast Fréchet distance between curves with long edges.  International Journal of Computational Geometry and Applications, 29:161–187, 2019.
  * [34] J. Gudmundsson, M.P. Seybold, and S. Wong.  Map matching queries on realistic input graphs under the Fréchet distance.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 1464–1492. SIAM, 2023.
  * [35] J. Gudmundsson, A. van Renssen, Z. Saeidi, and S. Wong.  Translation invariant Fréchet distance queries.  Algorithmica, 83(11):3514–3533, 2021.
  * [36] L.J. Guibas, J.E. Hershberger, J.S.B. Mitchell, and J.S. Snoeyink.  Approximating polygons and subdivisions with minimum-link paths.  International Journal of Computational Geometry & Applications, 3(4):383–415, 1993.
  * [37] S. Har-Peled.  Approximate nearest neighbor: towards removing the curse of dimensionality.  Theory of Computing, 8:321–350, 2012.
  * [38] J.E. Hershberger and J.S. Snoeyink.  An ${O}(n\log n)$ implementation of the Douglas-Peucker algorithm for line simplification.  In Proceedings of the Annual Symposium on Computational Geometry, pages 383–384, 1994.
  * [39] H. Imai and I. Masao.  Polygonal approximations of a curve—formulations and algorithms.  Machine Intelligence and Pattern Recognition, 6:71–86, 1988.
  * [40] P. Indyk.  Approximate nearest neighbor algorithms for Fréchet distance via product metrics.  In Proceedings of the Annual Symposium on Computational Geometry, pages 102–106, 2002.
  * [41] M. Jiang, Y. Xu, and B. Zhu.  Protein structure-structure alignment with discrete Fréchet distance.  Journal of Bioinformatics and Computational Biology, 6(1):51–64, 2008.
  * [42] M. Mirzanezhad.  On the approximate nearest neighbor queries among curves under the Fréchet distance, 2020.  arXiv:2004.08444.
  * [43] A. Nath and E. Taylor.  $k$-median clustering under discrete Fréchet and Hausdorff distances.  In Proceedings of the International Symposium on Computational Geometry, pages 58:1–58:15, 2020.
  * [44] R. Pollack and M.-F. 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.
  * [45] E. Sriraghavendra, K. Karthik, and C. Bhattacharyya.  Fréchet distance based approach for searching online handwritten documents.  In Proceedings of the International Conference on Document Analysis and Recognition, volume 1, pages 461–465, 2007.
  * [46] M. van de Kerkhof, I. Kostitsyna, M. Löffler, M. Mirzanezhad, and C. Wenk.  Global curve simplification.  In Proceedings of the European Symposium on Algorithms, pages 67:1–67:14, 2019.
  * [47] M. van Kreveld, M. Löffler, and L. Wiratma.  On optimal polyline simplification using the Hausdorff and Fréchet distance.  In Proceedings of the International Symposium on Computational Geometry, pages 56:1–56:14, 2018.
  * [48] M. Werner and D. Oliver.  ACM GIS Cup 2017: Range queries under Fréchet distance.  ACM SIGSPATIAL Special, 10(1):24–27, June 2018.