obtain $L_{i,j}^R$ if and only if $i' < i_\text{s}$. Therefore, we use the entry point instead of checking whether $L^R_{i,j}$ is a singleton. This process is analogous for horizontal boundaries of cells.

Earlier we assumed that each event in $\mathcal{E}$ ends at a different cell boundary. If events end at the same boundary, then these occur in the same row (or column) and it suffices to consider only the event that starts at the rightmost column (or highest row). This justifies the assumption and ensures that $\mathcal{E}$ contains $O(m n)$ events. Thus computing $e_\text{r}$ (Algorithm \[alg:findmatching\], line \[algline:find\_er\]) takes $O(m  n  \log(m  n))$ time, which is equal to the time needed to compute the [Fréchet distance]{}. Each recursion step splits the problem into two smaller problems, and the recursion ends when $mn \leq 1$. This results in an additional factor $m+n$. Thus the overall running time is $O((m+n) m  n  \log(m  n))$.

![Different sampling may result in different matchings.[]{data-label="fig:vertexdependency"}](vertexdependency)

#### Sampling and further restrictions

Two curves may still have many locally correct [Fréchet matching]{}s: the algorithm computes just one of these. However, introducing extra vertices may alter the result, even if these vertices do not modify the shape (see Fig. 