# 7 Discrete Fréchet distance Consider Professor Bille going

## Expert Answer

No answer yet for this question.

7 Discrete Fréchet distance Consider Professor Bille going for a walk with his personal dog. The professor
follows a path of points p,...,Pa and the dog follows a path of points qı,...9m. We assume that the walk is
partitioned into a number of small steps, where the professor and the dog in each step either both move from p,
tp p41 and from q, to q41, respectively, or only one of them moves and the other one stays.
The goal is to find the smallest possible length L of the leash, such that the professor and the dog can move
from p, and q,, resp., to p, and q. They cannot move backwards, and we only consider the distance between
points. The distance L is also known as the discrete Fréchet distance.
We let L(i, j) denote the smallest possible length of the leash, such that the professor and the dog can move
from p, and q, to P, and q,, resp. For two points p and q, let d(p,q) denote the distance between the them.
In the example below the dotted lines denote where Professor Bille (black nodes) and the dog (white nodes)
are at time 1 to 8. The minimum leash length is L = d(p1,q4).
P1
P2
P3
P4
Ps
96
94
7.1 Give a recursive formula for L(i, j).
7.2 Give pseudo code for an algorithm that computes the length of the shortest possible leash. Analyze space
and time usage of your solution.
7.3 Extend your algorithm to print out paths for the professor and the dog. The algorithm must return where
the professor and the dog is at each time step. Analyze the time and space usage of your solution.