\[fig:vertexdependency\]). This implies that the algorithm depends not only on the shape of the curves, but also on the sampling. Increasing the sampling further and further seems to result in a matching that decreases the matched distance as much as possible within a cell. However, since cells are rectangles, there is a slight preference for taking longer diagonal paths. Based on this idea, we are currently investigating “locally optimal” [Fréchet matching]{}s. The idea is to restrict to the locally correct [Fréchet matching]{} that decreases the matched distance as quickly as possible.

We also considered restricting to the “shortest” locally correct [Fréchet matching]{}, where “short” refers to the length of the path in the free space diagram. However, Fig. \[fig:lengthcounter\] shows that such a restriction does not necessarily improve the quality of the matching.

![Two locally correct Fréchet matchings for $P$ and $Q$. Right: shortest matching.[]{data-label="fig:lengthcounter"}](lengthcounter)

Locally correct discrete [Fréchet matching]{}s {#sec:discrete}
==============================================

Here we study the discrete variant of [Fréchet matching]{}s. For the discrete [Fréchet distance]{}, only the vertices of curves are matched. The discrete [Fréchet distance]{} can be computed in $O(m \cdot n)$ time via dynamic programming [@em-cdfd-94]. Here, we show how to also compute a locally correct discrete 