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 Rd, they prove a (1 + ε)-approximation in Õ(c n+ε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 + ε−1)(cnε−2 + c2mε−7 + ε−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 Rd in time O(c n+εm log n+ε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.