[Fréchet matching]{} in $O(m \cdot n)$ time.

#### Grids

Since we are interested only in matching vertices of the curves, we can convert the problem to a grid problem. Suppose we have two curves $P$ and $Q$ with $m$ and $n$ edges respectively. These convert into a grid $G$ of non-negative values with $m+1$ columns and $n+1$ rows. Every column corresponds to a vertex of $P$, every row to a vertex of $Q$. Any node of the grid $G[i,j]$ corresponds to the pair of vertices $(p_i, q_j)$. Its value is the distance between the vertices: $G[i,j] = |p_i - q_j|$. Analogous to free space diagrams, we assume that $G[0,0]$ is the bottomleft node and $G[m,n]$ the topright node.

#### Matchings

A monotonous path $\pi$ is a sequence of grid nodes $\pi(1), \ldots, \pi(k)$ such that every node $\pi(i)$ ($1 < i \leq k$) is the above, right, or above/right diagonal neighbor of $\pi(i-1)$. In the remainder of this section a path refers to a monotonous path unless indicated otherwise. A monotonous discrete matching of the curves corresponds to a path $\pi$ such that $\pi(1) = G[0,0]$ and $\pi(k) = G[m,n]$. We call a path $\pi$ locally correct if for all 