# Computing the Fr'echet Distance with a Retractable Leash

arXiv: https://arxiv.org/abs/1306.5527 · HTML: https://mlsanity.com/paper/1306.5527/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2013.

## Built on by (most cited first, 1 of 1)

- [An Unsupervised Learning Method with Convolutional Auto-Encoder for Vessel Trajectory Similarity Computation](https://mlsanity.com/paper/2101.03169/) (2021)

## Abstract (arXiv)

All known algorithms for the Fr'echet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fr'echet distance between polygonal curves in Rd under polyhedral distance functions (e.g., L1 and L_∞). We also get a (1+varepsilon)-approximation of the Fr'echet distance under the Euclidean metric, in quadratic time for any fixed varepsilon > 0. For the exact Euclidean case, our framework currently yields an algorithm with running time O(n2 log2 n). However, we conjecture that it may eventually lead to a faster exact algorithm.