Staying Close to a Curve
Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, Hamid Zarrabi-Zadeh · 2011
Given a point set S and a polygonal curve P in Rd, we study the problem of finding a polygonal curve through S, which has a minimum Fréchet distance to P. We present an efficient algorithm to solve the decision ver-sion of this problem in O(nk2) time, where n and k represent the sizes of P and S, respectively. A curve minimizing the Fréchet distance can be computed in O(nk2 log(nk)) time. As a by-product, we improve the map matching algorithm of Alt et al. by a log k factor for the case when the map is a complete graph. 1