20110201
Fréchet distance with speed limits
Publication
Publication
Computational Geometry , Volume 44  Issue 2 p. 110 120
In this paper, we introduce a new generalization of the wellknown Fréchet distance between two polygonal curves, and provide an efficient algorithm for computing it. The classical Fréchet distance between two polygonal curves corresponds to the maximum distance between two point objects that traverse the curves with arbitrary nonnegative speeds. Here, we consider a problem instance in which the speed of traversal along each segment of the curves is restricted to be within a specified range. We provide an efficient algorithm that decides in O(n2 logn) time whether the Fréchet distance with speed limits between two polygonal curves is at most ?, where n is the number of segments in the curves, and ≈ ≤0 is an input parameter. We then use our solution to this decision problem to find the exact Fréchet distance with speed limits in O(n2 log2 n) time.
Additional Metadata  

,  
doi.org/10.1016/j.comgeo.2010.09.008  
Computational Geometry  
Organisation  School of Computer Science 
Maheshwari, A, Sack, J.R, Shahbaz, K. (Kaveh), & ZarrabiZadeh, H. (Hamid). (2011). Fréchet distance with speed limits. In Computational Geometry (Vol. 44, pp. 110–120). doi:10.1016/j.comgeo.2010.09.008
