Fréchet Distance in the Imbalanced Case

In recent years, many works have studied approximation algorithms for the Fréchet distance [18, 26, 27]. This line of research culminated in the first constant-factor approximation algorithm for the Fréchet distance that runs in subquadratic time, due to Cheng, Huang, and Zhang [17]. Their randomized $(7+\epsilon )$-approximation algorithm for the continuous Fréchet distance runs in $𝒪(n{m}^{0.99}\log (n/\epsilon ))$ time for any $\epsilon >0$ and succeeds with probability at least $1-1/n^6$.

A simple idea to $3$-approximate the Fréchet distance between curves where $m=n^{\alpha }$ with $\alpha \in (0,1)$ in subquadratic time is the following. Compute a curve $P^{\prime }$ of complexity $n^{\prime }\in o(n)$ and its distance $\delta$ to $P$ such that every curve $Q$ of complexity $m$ has Fréchet distance at least $\delta$ to $P$. Then compute the Fréchet distance ${\delta }^{\prime }$ between $P^{\prime }$ and $Q$. Using triangle inequality, one can show that the Fréchet distance between $P$ and $Q$ is at least $\max \{{\delta }^{\prime }/2,\delta \}$ and at most $3\cdot \max \{{\delta }^{\prime }/2,\delta \}$, which yields a $3$-approximation. The difficulty of this approach is to compute such a curve $P^{\prime }$. Two related variants of this simplification problem have been studied. The first is computing an optimal $m$-simplification of $P$, that is, a curve $P^{\ast }$ of complexity at most $m$ minimizing the Fréchet distance to $P$ among all curves of complexity at most $m$. The second is computing an optimal $\delta$-simplification, that is, a curve $P^{\ast }$ of minimum complexity among all curves that have Fréchet distance at most $\delta$ to $P$. However, no previous result achieved a subquadratic running time for curves in arbitrary dimension when the approximation factor on the complexity of the simplified curve is constant [2, 4, 7, 13, 16, 22, 28].

A different approach to reduce the running time of computing the Fréchet distance is via Fréchet distance oracles. Such an oracle is a data structure that preprocesses an input curve and subsequently answers Fréchet distance queries with respect to query curves. Driemel and Har-Peled [19] described a data structure of size $𝒪(n\log n)$ using $𝒪(m^2\log n\log (m\log n))$ query time, which approximates the continuous Fréchet distance up to a (large) constant factor. For exact queries, [14] presented a data structure of size $𝒪{(nm)}^{\text{poly}(d,m)}$ and query time in $𝒪({(md)}^{𝒪(1)}\log (nm))$, where the query complexity $m$ is given at preprocessing time. Blank and Driemel [5] showed that for curves in 1D, there is a data structure of size $𝒪(n\log n)$ that computes the continuous Fréchet distance exactly in $𝒪(m^2{\log }^{2}n)$ time. For the discrete Fréchet distance, Filtser and Filtser [22] improved [20] and presented a data structure with size in $𝒪{(1/\epsilon )}^{kd}\log {(\epsilon )}^{-1}$ that approximates the discrete Fréchet distance within a factor of $(1+\epsilon )$ using expected $\widetilde{𝒪}(kd)$ query time, where $\widetilde{𝒪}(\cdot )$ hides polylogarithmic factors in $n$. Gudmundsson, Seybold, and Wong [24] used the lower bound construction by Bringmann [6] to show in a similar fashion to [8, 20, 25] the following. In 2D, there exists no Fréchet distance oracle with $\text{poly}(n)$ preprocessing time and $𝒪({(nm)}^{1-\delta })$ query time and approximation factor $1.001$ unless SETH fails.

Our first set of results shows lower bounds for algorithms that approximate the Fréchet distance conditioned on the Orthogonal Vectors Hypothesis (OVH). We show that the discrete Fréchet distance between 1-dimensional curves cannot be $(2-\epsilon )$-approximated in $𝒪({(nm)}^{1-\delta })$ time for any $\epsilon ,\delta >0$ unless OVH fails. This increases the approximation factor of $1.4-\epsilon$ by Bringmann and Mulzer [10]. Using a similar construction in 2D, we show that the continuous and discrete Fréchet distance cannot be approximated within a factor less than $1+\sqrt{2}$ (resp. $3$) when the curves lie in the Euclidean space (resp. in the $L_{\mathrm{\infty }}$-space) in $𝒪({(nm)}^{1-\delta })$. This leads to lower bounds for Fréchet distance oracles as well and answers an open question by [24].

To obtain this first set of results, we reduce from the Orthogonal Vector Problem: Given two sets of vectors $U,V\subset {\{0,1\}}^d$ of size $m$ and $n$, do there exist two vectors $u\in U$ and $v\in V$ such that $⟨u,v⟩=0$? Then, the results follow by OVH, which is implied by SETH [29, 9].

We construct a curve $P$ of complexity $𝒪(n+m)$ depending on $V$ and the size of $U$ and a curve $Q$ of complexity $𝒪(m)$ depending only on $U$. Then, we show that the Fréchet distance between $P$ and $Q$ is at most $1$ if and only if the OV instance has a solution. In order to get a lower bound also for the case where $n\gg m$, we construct $P$ such that the main part of $P$ lies in a ball of radius $1$. Hence, this main part can be matched to a single point of $Q$. Further, to obtain an inapproximability result of $2-\epsilon$ in 1D, the points of $P$ and $Q$ have integer coordinates. Hence, there are only three different values that the vertices of the main part of $P$ can have. This significantly restricts our possibilities to define $P$ and is the main difference to the construction by Bringmann and Mulzer [10]. They also note in their paper that obtaining a lower bound for an approximation factor of $1.4$ or higher requires a significantly different construction compared to theirs.

On the positive side, we present a data structure that preprocesses a 1-dimensional curve of complexity $n$ in $𝒪(n\log n)$ time using $𝒪(m)$ space that $2$-approximates the discrete Fréchet distance to query curves of complexity $m$ in $𝒪(m^2\log m)$ time. Hence, there exists a $2$-approximation algorithm for the discrete Fréchet distance in $𝒪(n\log n+m^2\log m)$ time matching our approximation factor lower bound and essentially the time lower bound by [12]. Secondly, we match our approximation factor lower bound in the $L_{\mathrm{\infty }}$-space by giving a simple $(3+\epsilon )$-approximation algorithm for the discrete and continuous Fréchet distance using $𝒪((n+m^2)\log n)$ time for curves in any dimension under any $L_p$-norm. Table 1 summarizes the results of this paper and related work.

For every construction of $P$ and $Q$, it holds that $d_{\text{dF}}(P^{\ast },Q^{\ast })\le 1$, $d_{\text{dF}}(P_s,Q^{\ast })\le 1$. Further, for $x,y\in \{0,1\}$ with $⟨x,y⟩=0$, it holds that $d_{\text{dF}}(P_x,Q_y)\le 1$. Then, we can match the following with Fréchet distance at most 1 and the lemma follows by Observation 2

$◀$

To show the other direction, we first prove some lemmas.

It holds that every second vertex of $Q^{\prime }$ is $-2$ and the vertices of value $-1$ on $P[s,t]$ are the only vertices on $P[s,t]$ within distance less than $2$ to those vertices of $Q^{\prime }$. Further, it holds that the vertices with value $-1$ of $P[s,t]$ have distance less than two only to the vertices of value $-2$ of $Q^{\prime }$. Hence, since the vertices of value $-1$ on $P[s,t]$ are exactly every second vertex on $P[s,t]$, we must traverse $P[s,t]$ and $Q^{\prime }$ synchronously. Therefore, if ${\sigma }_{\mathrm{\ell }}=0$ then ${\pi }_{\mathrm{\ell }}\in \{0,1\}$ and if ${\sigma }_{\mathrm{\ell }}=1$ then ${\pi }_{\mathrm{\ell }}=0$ by construction. $◀$

In 2D, we also want to show a bound for the continuous Fréchet distance. Then the vertices of $Q$ can also be matched to points on edges of $P$. We use the notation of the following subcurve of $P_0$ (resp. $P_1$): $P_0^{\prime }=⟨a_4,a_5,\mathrm{\dots },a_8,\mathrm{\dots },a_4⟩$ (resp. $P_1^{\prime }=⟨a_4,\mathrm{\dots },a_8,a_1,a_2,a_1,a_8,\mathrm{\dots },a_4⟩$).

We show this lemma by constructing paths in the non-free space for $\delta =1+c$ (see Figure 3). First observe that $\Vert 2a_i-a_j\Vert \ge 1+c$ for any $i,j\in \{1,\mathrm{\dots },8\}$ with $i-j\ge 3mod8$.

Assume that the first (resp. last) vertex of $Q_y$ is matched to a point on a subcurve $P_x^{\prime }$ with $x\in \{0,1\}$. Then, there must exist a path completely contained in the free space ending at the last (resp. first) vertex of $Q_y$. This cannot be the case since there exists a continuous matching between $P_x^{\prime }$ and $⟨2a_1,2a_2\mathrm{\dots },2a_5,\mathrm{\dots },2a_1⟩$ that is completely contained in the non-free space (see the red paths in Figure 3). Therefore, the first as well as the last vertex of $Q_y$ has to be matched to a point on a subcurve $P^{\prime \prime }$ of $P$ such that $P^{\prime \prime }=⟨a_4,a_3,a_2,a_1,a_2,a_3,a_4⟩$.

Next, we show that $P^{\prime }$ contains exactly one $P_x^{\prime }$ as a subcurve. Since $\Vert c{a}_1-a_5\Vert \ge 1+c$ (resp. $\Vert \tilde{a}-a_5\Vert \ge 1+c$), there exists a path that is completely contained in the non-free space between $⟨a_5,a_4,\mathrm{\dots }{a}_2,a_1,a_2,\mathrm{\dots },a_4,a_5⟩$ and $⟨2a_8,c{a}_1,2a_8,2a_7,\mathrm{\dots },2a_4,2a_5,\mathrm{\dots },2a_8,c{a}_1,2a_8⟩$(resp. $⟨\tilde{a},2a_7,\mathrm{\dots },2a_4,2a_5,\mathrm{\dots },\tilde{a}⟩$) (see the orange paths in Figure 3). Hence by construction of $P$, it follows that $P_x^{\prime }$ is a subcurve of $P^{\prime }$ and $P^{\prime }$ is a subcurve of $⟨a_4,a_3,a_2⟩\circ P_x\circ ⟨a_2,a_3,a_4⟩$ with $x\in \{0,1\}$. It remains to show that $x\ne 1$, if $y=1$. This follows since the distance between $a_2$ and $2a_7$, $\tilde{a}$, $2a_7$ is at least $1+c$ (see the pink path in Figure 3). $◀$ The next lemma follows directly by the construction of the curves and Lemma 6.

Let $M$ be a discrete (resp. continuous) matching that realizes the discrete (resp. continuous) Fréchet distance between $P$ and $Q$. Assume that (resp. ), then in the matching $M$, the two points of value $P_{null}$ of $P$ must be matched to two distinct points $q_1,q_2$ on $Q$ both on an edge that contains the value $Q_{null}$, since they are the only points within distance at most $1+c\le 3$ to $P_{null}$. Let $P_0^{\prime }=P_0$ and $P_1^{\prime }=P_1$ in the 1D setting. Define $j$ such that $q_1$ is contained on an incident edge to the $j$-th $Q_{null}$ on $Q$. Then, the first ${(Q_1)}^{d+1}$ after the $j$-th $Q_{null}$ on $Q$ must be matched to a subcurve $P^{\prime }$ of $P$ such that $P_1^{\prime }\circ {(P_0)}^{d+1}\circ P_1^{\prime }$ is a subcurve of $P^{\prime }$ by Lemma 5 and Lemma 7. The only time we have ${(P_0)}^{d+1}$ in $P$ is before $P_1\circ {○}_{\mathrm{\ell }=1}^d{P}_{v_{i\mathrm{\ell }}}$ for an $i$. Hence by Lemma 5 and Lemma 7, there exists an index $i$ such that in the matching $M$ the subcurve $P_{v_{i,1}}^{\prime }\circ {○}_{\mathrm{\ell }=2}^{d-1}{P}_{v_{i,\mathrm{\ell }}}\circ P_{v_{i,d}}^{\prime }$ is matched to a subcurve of ${○}_{\mathrm{\ell }=1}^d{Q}_{u_{j,\mathrm{\ell }}}$ and $v_{i,\mathrm{\ell }}=0$ if $u_{j,\mathrm{\ell }}=1$. Hence, it holds that $⟨v_i,u_j⟩=0$. $◀$ By Lemma 4 and Lemma 8 together with Observation 3, the next two theorems follow.

Our construction gives also a bound on Fréchet distance oracles (proof in the full version).

Define ${\delta }_m=\min \{d_{\text{dF}}(P,Q)\mid Q\text{ has complexity }m\}$. We want to compute a curve $P^{\prime }$ such that $d_{\text{dF}}(P,P^{\prime })\le {\delta }_m/2$. The complexity of $P^{\prime }$ might be $n$, but it should be possible to store a compact description of $P^{\prime }$ in $𝒪(m)$ space. To compute $P^{\prime }$, we first compute the optimal $m$-simplification $P^{\ast }$ of $P$ for the discrete Fréchet distance. The curve $P^{\ast }$ is computed via searching over the possible values $\delta$ for ${\delta }_m$ and then computing the optimal $\delta$-simplification. We compute the optimal $\delta$-simplification of $P$ using Algorithm 1. It begins by finding the longest prefix $P[1,i_1]$ that is contained in a $2\delta$-interval, whose center becomes the first vertex of the $\delta$-simplification. Then, it continues by finding the largest index $i_2$ such that $P[i_1+1,i_2]$ is contained in a $2\delta$-interval and again the center of this interval is added to the $\delta$-simplification. This process is repeated until the final vertex of $P$ is reached.

The proof of the following lemma is in the full version.

If the complexity of the $\delta$-simplification is greater than $m$, it holds that ${\delta }_m>\delta$. Otherwise, ${\delta }_m\le \delta$. In contrast to higher dimensions, the optimal $m$-simplification for any $m$ of a 1-dimensional curve $P$ has distance ${\delta }_m\in \{|P(i)-P(j)|/2\mid i,j\in \{1,\mathrm{\dots },n\}\}$ to $P$, where the distance is only defined by two vertices of $P$. By Frederickson and Johnson [23], we can search over all possible values for ${\delta }_m$ using $𝒪(\log n)$ calls of Algorithm 1 and get the following lemma.

Let $P^{\ast }=⟨p_1,\mathrm{\dots },p_{\mathrm{\ell }}⟩$ be an optimal $m$-simplification of $P$. Let $M$ be the discrete matching between $P$ and $P^{\ast }$ computed by Algorithm 1, and $P(i_j)$ be the last vertex of $P$ that is matched to $p_j$; i.e. $M=((1,1),(2,1)\mathrm{\dots },(i_1,1),$ $(i_1+1,2),(i_1+2,2),\mathrm{\dots },(i_2,2),(i_2+1,3),\mathrm{\dots },(i_{\mathrm{\ell }},\mathrm{\ell }))$. We construct a curve $P^{\prime }$ that has discrete Fréchet distance at most ${\delta }_m/2$ to $P$ and can be stored in a compressed way using $𝒪(m)$ space (see Figure 4). We call $P^{\prime }$ a compressed simplification. For every $(x,y)\in M$, define $r_x=p_y-{\delta }_m/2$ if and $r_x=p_y+{\delta }_m/2$ otherwise. Then, it holds that $|r_x-P(x)|\le {\delta }_m/2$. The compressed simplification $P^{\prime }$ is $⟨r_1,\mathrm{\dots },r_n⟩$ after deleting the vertices with identical predecessor, so that $P^{\prime }$ contains $r_i$ only if $r_i\ne r_{i-1}$. For every $j$, we count the total number $k_j$ that $P^{\prime }$ contains $p_j\pm {\delta }_m/2$ and define $z_j\in \{-1,1\}$ such that the first time $P^{\prime }$ contains $p_j+z_j{\delta }_m/2$ is before $P^{\prime }$ contains $p_j-z_j{\delta }_m/2$. Therefore, the values $p_1,\mathrm{\dots },p_{\mathrm{\ell }}$, $k_1,\mathrm{\dots },k_{\mathrm{\ell }}$, $z_1,\mathrm{\dots },z_{\mathrm{\ell }}$, and ${\delta }_m$ fully describe $P^{\prime }$. The next lemma follows directly by construction and $\mathrm{\ell }\le m$.

In the following, we give a $2$-approximation query algorithm for the discrete Fréchet distance between $P$ and any query curve $Q$ of complexity $m$. We use the precomputed compressed simplification $P^{\prime }$ and compute $d_{\text{dF}}(P^{\prime },Q)$ if it is at least $\frac{3}{2}{\delta }_m$.

By definition of ${\delta }_m$, it holds that $d_{\text{dF}}(P,Q)\ge {\delta }_m$ for every curve $Q$ of complexity $m$. Further, by Lemma 14 it holds that $d_{\text{dF}}(P,P^{\prime })\le {\delta }_m/2$. Hence, if $d_{\text{dF}}(P^{\prime },Q)\le \frac{3}{2}{\delta }_m$, then

Otherwise, it holds that $\frac{3}{2}\delta =d_{\text{dF}}(P^{\prime },Q)>\frac{3}{2}{\delta }_m$. Hence, $\delta >{\delta }_m$. Therefore,