---
abstract: 'The [Fréchet distance]{} is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the [Fréchet distance]{} a [Fréchet matching]{}. There are often many different [Fréchet matching]{}s and not all of these capture the similarity between the curves well. We propose to restrict the set of [Fréchet matching]{}s to “natural” matchings and to this end introduce *locally correct* [Fréchet matching]{}s. We prove that at least one such matching exists for two polygonal curves and give an $O(N^3 \log N)$ algorithm to compute it, where $N$ is the total number of edges in both curves. We also present an $O(N^2)$ algorithm to compute a locally correct discrete [Fréchet matching]{}.'
author:
- Kevin Buchin
- Maike Buchin
- Wouter Meulemans
- Bettina Speckmann
bibliography:
- 'references.bib'
title: 'Locally Correct Fréchet Matchings[^1]'
---

Introduction {#sec:introduction}
============

Many problems ask for the comparison of two curves. Consequently, several distance measures have been proposed for the similarity of two curves $P$ and $Q$, for example, the Hausdorff and the [Fréchet distance]{}. Such a distance measure simply returns a number indicating the (dis)similarity. However, the Hausdorff and the [Fréchet distance]{} are both 