Approximating the Fréchet distance when only one curve is $c$-packed

Abstract

One approach to studying the Fréchet distance is to consider curves that satisfy realistic assumptions. By now, the most popular realistic assumption for curves is $c$-packedness. Existing algorithms for computing the Fréchet distance between $c$-packed curves require both curves to be $c$-packed. In this paper, we only require one of the two curves to be $c$-packed. Our result is a nearly-linear time algorithm that $(1+\epsilon )$-approximates the Fréchet distance between a $c$-packed curve and a general curve in ${\mathbb{R}}^d$, for constant values of $\epsilon$, $d$ and $c$.

To appear in ISAAC 2024