[@Wylie2012] and detecting patterns in movement data [@bbgll-dcpcs-11], would profit from good [Fréchet matching]{}s.

![Two Fréchet matchings for curves $P$ and $Q$.[]{data-label="fig:badmatch"}](badmatch)

![Two Fréchet matchings. Right: the result of speed limits is not locally correct.[]{data-label="fig:speedcounter"}](speedcounter)

#### Results

We restrict the set of [Fréchet matching]{}s to “natural” matchings by introducing *locally correct* [Fréchet matching]{}s: matchings that for any two matched subcurves are again a [Fréchet matching]{} on these subcurves. In Section \[sec:lcm\] we prove that there exists such a locally correct [Fréchet matching]{} for any two polygonal curves. Based on this proof we describe in Section \[sec:algorithm\] an $O(N^3 \log N)$ algorithm to compute such a matching, where $N$ is the total number of edges in both curves. We consider the discrete [Fréchet distance]{} in Section \[sec:discrete\] and give an $O(N^2)$ algorithm to compute locally correct matchings under this metric.

#### Related work

The first algorithm to compute the [Fréchet distance]{} was given by Alt and Godau [@Alt1995]. They also consider a non-monotone [Fréchet distance]{} and their algorithm for this variant results in a locally correct non-monotone matching (see Remark 3.5 in [@hr-fdre-12]). Eiter and Mannila gave the first algorithm to compute the discrete [Fréchet distance]{} [@em-cdfd-94]. Since then, the [Fréchet 