We describe the first strongly subquadratic time algorithm with subexponential approximation ratio
for approximately computing the Fréchet distance between two polygonal chains.
Specifically, let \(P\) and \(Q\) be two polygonal chains with \(n\) vertices in \(d\)-dimensional
Euclidean space, and let \(\alpha \in [\sqrt{n}, n]\).
Our algorithm deterministically finds an \(O(\alpha)\)-approximate Fréchet correspondence in
time \(O((n^3 / \alpha^2) \log n)\).
In particular, we get an \(O(n)\)-approximation in near-linear \(O(n \log n)\) time, a vast
improvement over the previously best know result, a linear time \(2^{O(n)}\)-approximation.
As part of our algorithm, we also describe how to turn any approximate decision
procedure for the Fréchet distance into an approximate optimization algorithm whose
approximation ratio is the same up to arbitrarily small constant factors.
The transformation into an approximate optimization algorithm increases the running time of the
decision procedure by only an \(O(\log n)\) factor.