Approximating the Fr\'echet distance when only one curve is $c$-packed
<|reference_start|>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+\varepsilon)$-approximates the Fr\'echet distance between a $c$-packed curve and a general curve in $\mathbb R^d$, for constant values of $\varepsilon$, $d$ and $c$.<|reference_end|>
@article{gudmundsson2024approximating,
    title={Approximating the Fr\'echet distance when only one curve is $c$-packed},
    author={Joachim Gudmundsson, Tiancheng Mai, Sampson Wong},
    journal={arXiv preprint arXiv:2407.05114},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05114},
    primaryClass={cs.CG}
}