Computing the Fréchet Distance When Just One Curve is $c$-Packed: A Simple Almost-Tight Algorithm

Abstract

We study approximating the continuous Fréchet distance of two curves with complexity $n$ and $m$, under the assumption that only one of the two curves is $c$-packed. Driemel, Har{-}Peled and Wenk DCG'12 studied Fréchet distance approximations under the assumption that both curves are $c$-packed. In ${\mathbb{R}}^d$, they prove a $(1+\epsilon )$-approximation in $\tilde{O}(dc\frac{n+m}{\epsilon })$ time. Bringmann and Künnemann IJCGA'17 improved this to $\tilde{O}(c\frac{n+m}{\sqrt{\epsilon }})$ time, which they showed is near-tight under SETH. Recently, Gudmundsson, Mai, and Wong ISAAC'24 studied our setting where only one of the curves is $c$-packed. They provide an involved $\tilde{O}(d\cdot (c+{\epsilon }^{-1})(cn{\epsilon }^{-2}+c^{2}m{\epsilon }^{-7}+{\epsilon }^{-2d-1}))$-time algorithm when the $c$-packed curve has $n$ vertices and the arbitrary curve has $m$, where $d$ is the dimension in Euclidean space. In this paper, we show a simple technique to compute a $(1+\epsilon )$-approximation in ${\mathbb{R}}^d$ in time $O(d\cdot c\frac{n+m}{\epsilon }\log \frac{n+m}{\epsilon })$ when one of the curves is $c$-packed. Our approach is not only simpler than previous work, but also significantly improves the dependencies on $c$, $\epsilon$, and $d$. Moreover, it almost matches the asymptotically tight bound for when both curves are $c$-packed. Our algorithm is robust in the sense that it does not require knowledge of $c$, nor information about which of the two input curves is $c$-packed.