Fréchet Distance in the Imbalanced Case

Given two polygonal curves $P$ and $Q$ defined by $n$ and $m$ vertices with $m\le n$, we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of $2-\epsilon$ in $\mathcal{O}((nm{)}^{1-\delta })$ time for any $\epsilon ,\delta >0$ unless OVH fails. Using a similar construction, we extend this bound for curves in 2D under the continuous or discrete Fréchet distance and increase the approximation factor to $1+\sqrt{2}-\epsilon$ (resp. $3-\epsilon$) if the curves lie in the Euclidean space (resp. in the $L_{\mathrm{\infty }}$-space). This strengthens the lower bound by Buchin, Ophelders, and Speckmann to the case where $m=n^{\alpha }$ for $\alpha \in (0,1)$ and increases the approximation factor of $1.001$ by Bringmann. For the discrete Fréchet distance in 1D, we provide an approximation algorithm with optimal approximation factor and almost optimal running time. Further, for curves in any dimension embedded in any $L_p$ space, we present a $(3+\epsilon )$-approximation algorithm for the continuous and discrete Fréchet distance using $\mathcal{O}((n+m^2)\log n)$ time, which almost matches the approximation factor of the lower bound for the $L_{\mathrm{\infty }}$ metric.