Matching Polygonal Curves with Respect to the Frechet Distance

摘要

We provide the first algorithm for matching two polygonal curves P and Q under translations with respect to the Frechet distance. If P and Q consist of m and n segments, respectively, the algorithm has runtime O((mn)~3(m + n)~2 log(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 Frechet 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((ε~(-2)mn).