Approximating the Fr\'echet distance when only one curve is c-packed

One approach to studying the Fr\'echet 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\'echet 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+ε)-approximates the Fr\'echet distance between a c-packed curve and a general curve in Rᵈ, for constant values of ε, d and c.