Matching Polygonal Curves with Respect to the Fréchet Distance

We provide the first algorithm for matching two polygonal curves P and Q under translations with respect to the Fréchet distance. If P and Q consist of m and n segments, respectively, the algorithm has runtime O((mn)3(m+n)2log(m+n)). We also present an algorithm giving an approximate solution as an alternative. To this end, we generalize the notion of a reference point and observe that all reference points for the Hausdorff distance are also reference points for the Fréchet distance. Furthermore we give a new reference point that is substantially better than all known reference points for the Hausdorff distance. These results yield a (1 + ∈)-approximation algorithm for the matching problem that has runtime O(∈-2mn).