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 Fréchet 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 Fréchet distance problem, including the Fréchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the particular case in which the map is a directed acyclic graph.
|Keywords||Closed curves, Free-space map, Fréchet distance, Partial curve matching|
Maheshwari, A, Sack, J.-R, Shahbaz, K. (Kaveh), & Zarrabi-Zadeh, H. (Hamid). (2014). Improved algorithms for partial curve matching. Algorithmica, 69(3), 641–657. doi:10.1007/s00453-013-9758-3