Improved Algorithms for Partial Curve Matching
We revisit the problem of deciding whether a given curve resembles some part of a larger curve under a fixed Frchet distance, achieving a running time of O(nm), for n and m being the number of segments in the two curves. This improves the long-standing result of Alt and Godau by an O(log(nm)) factor. Our solution is based on constructing a simple data structure which we call free-space map. Using this data structure, we obtain improved algorithms for several variants of the Frchet distance problem, including the Frchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt etal. for the particular case in which the map is a directed acyclic graph.
partial curve matching frchet distance free-space map closed curves