The Frechet distance measures similarity between two curves $f$ and $g$ that takes into account the ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along $f$, and its owner, walking along $g$, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Frechet distance replaces the dog and its owner by a pair of frogs that can only reside on $m$ and $n$ specific stones, respectively. The stones are in fact sequences of points, typically sampled from the respective curves $f$ and $g$. These frogs hop from one stone to the next without backtracking, and the discrete Frechet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops from the starting points to the terminal points of their sequences. The discrete Frechet distance can be computed in $O(mn)$ time by a straightforward dynamic programming algorithm. We present ...
['Pankaj K. Agarwal', 'Rinat Ben Avraham', 'Haim Kaplan', 'Micha Sharir']
Computing the Discrete Fréchet Distance in Subquadratic Time