based on matchings of the points on the curves. The distance returned is the maximum distance between any two matched points. The [Fréchet distance]{} uses *monotonous matchings* (and limits of these): if point $p$ on $P$ and $q$ on $Q$ are matched, then any point on $P$ after $p$ must be matched to $q$ or a point on $Q$ after $q$. The *[Fréchet distance]{}* is the maximal distance between two matched points minimized over all monotonous matchings of the curves. Restricting to monotonous matchings of only the vertices results in the *discrete [Fréchet distance]{}*. We call a matching resulting in the (discrete) [Fréchet distance]{} a *(discrete) [Fréchet matching]{}*. See Section \[sec:prelims\] for more details.

There are often many different [Fréchet matching]{}s for two curves. However, as the [Fréchet distance]{} is determined only by the maximal distance, not all of these matchings capture the similarity between the curves well (see Fig. \[fig:badmatch\]). There are applications that directly use a matching, for example, to map a GPS track to a street network [@Wenk2006] or to morph between the curves [@Efrat2002]. In such situations a “good” matching is important. We believe that many applications of the (discrete) [Fréchet distance]{}, such as protein alignment 