The Quick Dog Jumps the Log
We give linear-time, and thus optimal, (1+{$\epsilon$})-approximation algorithms for numerous variants of the Fr{\’e}chet distance between c-packed curves (where c {$\in$} O(1)), removing an additional log factor that was present in previous algorithms. The key to our new algorithms is a linear-size approximation of the elevation function, which uses a decomposition of the domain into rectangles, and a careful implicit dynamic programming on this decomposition. The algorithm extends to the strong, weak, discrete, and continuous Fr{\’e}chet distances with a running time of roughly O(cn/{$\epsilon$}). The c-packedness assumption is used only in the analysis, and the algorithm is simple and should work efficiently for other inputs.
- Published in:
arXiv - Type:
Article - Authors:
- Year:
2026 - Source:
https://arxiv.org/pdf/2607.09917
Citation information
: The Quick Dog Jumps the Log, arXiv, 2026, July, https://arxiv.org/pdf/2607.09917, Blank.etal.2026b,
@Article{Blank.etal.2026b,
author={Blank, Lotte; Driemel, Anne; Har-Peled, Sariel; Richter, Marena},
title={The Quick Dog Jumps the Log},
journal={arXiv},
month={July},
url={https://arxiv.org/pdf/2607.09917},
year={2026},
abstract={We give linear-time, and thus optimal, (1+{$\epsilon$})-approximation algorithms for numerous variants of the Fr{\’e}chet distance between c-packed curves (where c {$\in$} O(1)), removing an additional log factor that was present in previous algorithms. The key to our new algorithms is a linear-size approximation of the elevation function, which uses a decomposition of the domain into...}}
