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 Kunnemann IJCG’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.