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 R^d, they prove a (1 + ε)-approximation in Õ(c ⁿ⁺_ε^m ) time. Bringmann and Künnemann IJCGA’17 improved this to Õ(c ^n√+_ε^m ) 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 Õ((c + ε⁻¹)(cnε⁻² + c²mε⁻⁷ + ε^−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 + ε)-approximation in R^d in time O(c ⁿ⁺_ε^m log ⁿ⁺_ε^m ) 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, ε, 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.