# Computing the discrete Fréchet distance using dynamic programming

## Definition

The Fréchet distance is usually explained using the analogy of a man walking his dog.

A man is walking a dog on a leash: the man can move on one curve, the dog on the other; both may vary their speed, but backtracking is not allowed. What is the length of the shortest leash that is sufficient for traversing both curves?

## Intuition

We can formally define it as:

Given two sequence of points in $$\mathbb{R}^d$$, p={p1, p2, p3…..pn} and q= {q1, q2, q3…. qm}, Fréchet distance represented by $$f(x,y)$$ is the maximum of the minimum distances between points pi and qi. To understand it more intuitively, let us look at a simple example.

In the below graph, I have two set of polylines with positions:

$$P = {(2,1) , (3,1), (4,2), (5,1)}$$
$$Q = {(2,0),(3,0),(4,0)}$$

Starting and ending points being (p1,q1) and (p4,q3) respectively.

We find all the pairs of walks between p and q given as,

$$p1 -> (p1, q1) , (p1,q2), (p1,q3)$$
$$p2 -> (p2, q1), (p2,q2), (p2,q3)$$
$$p3 -> (p3, q2), (p3,q2), (p3,q3)$$
$$p4 -> (p4, q2), (p4,q2), (p4,q3)$$

then, we find the minimum distances for each pair.

$$min\{p1\} = min\{dist(p1,q1), dist(p1,q2), dist(p1,q3)\} = min\{1, 1.4, 2.2\} = 1$$
$$min\{p2\} = min\{dist(p2,q1), dist(p2,q2), dist(p2,q3)\} = min\{1.4, 1, 1.4\} = 1$$
$$min\{p3\} = min\{dist(p3,q1), dist(p3,q2), dist(p3,q3)\} = min\{2.8, 2.2, 2\} = 2 \}$$
$$min\{p4\} = min\{dist(p3,q1), dist(p3,q2), dist(p3,q3)\} = min\{3.2, 2.2, 2\} = 2$$

Now, we can find the Fréchet distance by finding the maximum of all the minimums we calculated in the last step.

$$f(x,y) = max\{min\{p1\}, min\{p2\}, min\{p3\}, min\{p4\}\} = max\{1,1,2,2\} = 2$$

## Implementation

The implementation described by Thomas Eiter and Heikki Mannila  uses dynamic programming to reduce the time complexity of finding the Fréchet distance by navigating through only three possible paths.

• P and Q both move one step
• P stays where it is, Q moves one step
• P moves one step, Q stays where it is

This reduces the total number of pairs for each point in P. The implementation is as below:

from scipy.spatial.distance import euclidean
import seaborn as sns

P = [[2,1] , [3,1], [4,2], [5,1]]
Q = [[2,0] , [3,0], [4,0]]

p_length = len(P)
q_length = len(Q)
distance_matrix = np.ones((p_length, q_length)) * -1

# fill the first value with the distance between
# the first two points in P and Q
distance_matrix[0, 0] = euclidean(P, Q)

# load the first column and first row with distances (memorize)
for i in range(1, p_length):
distance_matrix[i, 0] = max(distance_matrix[i-1, 0], euclidean(P[i], Q))
for j in range(1, q_length):
distance_matrix[0, j] = max(distance_matrix[0, j-1], euclidean(P, Q[j]))

for i in range(1, p_length):
for j in range(1, q_length):
distance_matrix[i, j] = max(min(distance_matrix[i-1, j], distance_matrix[i, j-1], distance_matrix[i-1, j-1]),
euclidean(P[i], Q[j]))
distance_matrix[p_length-1, q_length-1]
sns.heatmap(distance_matrix, annot=True)

The preview of our sample as a heatmap is as below: