2026/07/10 by Lotte Blank, Anne Driemel, Sariel Har-Peled +1 · 1 voice
#cs.CG
We give linear-time, and thus optimal, (1+ε)-approximation algorithms for numerous variants of the Frechet distance between c-packed curves (where c ∈ 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 Frechet distances with a running time of roughly O(cn/ε). The c-packedness assumption is used only in the analysis, and the algorithm is simple and should work efficiently for other inputs.