We propose a new measure to capture similarity between polygonal curves, called the minimum backward Fréchet distance. It is a natural optimization on the weak Fréchet distance, a variant of the well-known Fréchet distance. More specifically, for a given threshold ε, we are searching for a pair of walks for two entities on the two input curves, T1 and T2, such that the union of the portions of backward movements is minimized and the distance between the two entities, at any time during the walk, is less than or equal to ". Our algorithm detects if no such pair of walks exists. This natural optimization problem appears in many applications in Geographical Information Systems, mobile networks and robotics. We provide an exact algorithm with time complexity of Ο (n2 log n) and space complexity of Ο (n2), where n is the maximum number of segments in the input polygonal curves.

Additional Metadata
Keywords Fréchet Distance, Optimization, Polygonal Curves Similarity
Persistent URL dx.doi.org/10.1145/2666310.2666418
Conference 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014
Citation
Gheibi, A. (Amin), Maheshwari, A, Sack, J.-R, & Scheffer, C. (Christian). (2014). Minimum backward fréchet distance. Presented at the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014. doi:10.1145/2666310.2666418