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){sup}3log(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(ε{sup}-2mn).