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

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 + \varepsilon)$-approximation in $\tilde{O}\!\left( c{\frac{n+m}{\varepsilon}} \right)$ time. Bringmann and Künnemann IJCGA’17 improved this to $\tilde{O}\!\left( c{\frac{n+m}{\sqrt\varepsilon}} \right)$ time, which they showed is near-tight under SETH. Both algorithms have a hidden exponential dependency on the dimension d. 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}((c + \varepsilon^{-1})(cn\varepsilon^{-2} + c^{+2}m\varepsilon^{-7} + \varepsilon^{-2d-1}))$-time algorithm when the c-packed curve has n vertices and the arbitrary curve has m. In this paper, we show a simple technique to compute a $(1 + \varepsilon)$-approximation in $\mathbb{R}^d$ in time ${O}( c{\frac{n+m}{\varepsilon}}\log {\frac{n+m}{\varepsilon}})$ 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, $\varepsilon$, and d (which is only linear). 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.