The minimum backward Fréchet distance (MBFD) problem is a natural optimization problem for the weak Fréchet distance, a variant of the well-known Fréchet distance. In this problem, a threshold ε and two polygonal curves, T 1 and T 2 , are given. The objective is to find a pair of walks on T 1 and T 2 , which minimizes the union of the portions of backward movements (backtracking) while maintaining, at any time, a distance between the moving entities of at most ε. In this paper, we generalize this model to capture scenarios when the cost of backtracking on the input polygonal curves is not homogeneous. More specifically, each edge of T 1 and T 2 has an associated non-negative weight. The cost of backtracking on an edge is the Euclidean length of backward movement on that edge multiplied by the corresponding weight. The objective is to find a pair of walks that minimizes the sum of the costs on the edges of the curves, while guaranteeing that the weak traversal of the curves maintains a weak Fréchet distance of at most ε. We propose two exact algorithms, a simple algorithm with O(n 4 ) time and space complexities and an improved algorithm whose time and space complexities are O(n 2 log 3/2 ⁡n), where n is the maximum number of the edges of T 1 and T 2 . A solution to weighted MBFD also implies a solution to the more general optimization problem in which both backward and forward movements have associated costs.

Additional Metadata
Keywords Backtracking, Computational geometry, Fréchet distance, Shortest path, Similarity measures, Visibility graph, Weighted polygonal curves
Persistent URL dx.doi.org/10.1016/j.tcs.2019.03.015
Journal Theoretical Computer Science
Citation
Gheibi, A. (Amin), Maheshwari, A, & Sack, J.-R. (Jörg-Rüdiger). (2019). Weighted minimum backward Fréchet distance. Theoretical Computer Science. doi:10.1016/j.tcs.2019.03.015