Weighted Minimum Backward Frechet Distance.
Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack · Canadian Conference on Computational Geometry · 2015
The minimum backward Frechet distance (MBFD) problem is a natural optimization problem for the weak Frechet distance, a variant of the well-known Frechet distance. In this problem, a threshold e 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 e. 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 Frechet distance of at most e. 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.