algorithm. This section is devoted to proving the following theorem.

Algorithm \[alg:findmatching\] computes a locally correct [Fréchet matching]{} of two polygonal curves $P$ and $Q$ with $m$ and $n$ edges in $O((m+n) m n \log (mn))$ time.

$P$ and $Q$ are curves with $m$ and $n$ edges A locally correct [Fréchet matching]{} for $P$ and $Q$

$(\sigma, \theta)$ where $\sigma(t) = t \cdot m$, $\theta(t) = t \cdot n$ $(\sigma, \theta)$ where $\sigma(t) = \theta(t) = t$ Find event $e_\text{r}$ of a minimal realizing set \[algline:find\_er\] Split $P$ into $P_1$ and $P_2$ according to $e_\text{r}$ Split $Q$ into $Q_1$ and $Q_2$ according to $e_\text{r}$ $\mu_1 \rightarrow \texttt{ComputeLCFM}(P_1, Q_1)$ $\mu_2 \rightarrow \texttt{ComputeLCFM}(P_2, Q_2)$ concatenation of $\mu_1$, $e_\text{r}$, and $\mu_2$

Using the notation of Alt and Godau [@Alt1995], $L^F_{i,j}$ denotes the interval of free space on the left boundary of cell $(i,j)$; $L^R_{i,j}$ denotes the subset of $L^F_{i,j}$ that is reachable from point $(0,0)$ of the free space diagram with a monotonous path in the free space. Analogously, $B^F_{i,j}$ and $B^R_{i,j}$ are defined for the bottom boundary.

With a slight modification to the decision algorithm, we can compute the minimal value of $\varepsilon$ such that a path is available from cell $(1,1)$ 