Compute Frechet distance

Question

IF there are two curves P [p1,p2...pm] and Q [q1,q2...qm]. To compute the Frechet distance, we will arrange them in the form of grid and compute distance between different points in the grid and fill the cells. What is to be done next. How do we reach upto Frechet distance

Answer 1

The standard approach is to use a recursive solution known as dynamic programming (a type of memoization).

Your problem, computing the discrete Fréchet distance, is very close to a technique known as Dynamic Time Warping (DTW). In this context, your distance grid would be known as the ground distance matrix, defined by

$$d_{p,q}=||P_p-Q_q||$$

If we define $D_{p,q}$ to be the discrete Fréchet distance between $[P_1,\ldots,P_p]$ and $[Q_1,\ldots,Q_q]$, then the following recursion holds:

$$D_{p,q}=\max\{d_{p,q},\min\{D_{p-1,q},D_{p,q-1},D_{p-1,q-1}\}\}$$

That is, the maximum inter-curve distance either occurs at the current pair of $(p,q)$ points, or it occured prior to this along the path (i.e. further back). In the latter case, the no-backtracking requirement means that the least-cost path must have arrived at $(p,q)$ from one of the three neighbors $(p-1,q),(p,q-1),(p-1,q-1)$.

To compute the distance, you fill up the table of $D_{p,q}$ values iteratively, beginning at $D_{1,1}$ and ending at $D_{m,n}$ (where $n-m$ in your case).

The Wikipedia page links to a paper describing the details of this approach:

Eiter, T., & Mannila, H. (1994). Computing discrete Fréchet distance. Tech. Report CD-TR 94/64, Information Systems Department, Technical University of Vienna.

(Note that Dynamic Time Warping is exactly the same, except the $\max$ operation is replaced by $+$.)