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.

, , , , , ,
Theoretical Computer Science
Computational Geometry Lab

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