Computing Fréchet Distance with Speed Limits.
Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz · 2009
In this paper, we study a problem on computing the Fréchet distance between two polygonal curves and provide efficient solutions for solving it. In the classical Fréchet distance, point objects move arbitrarily fast on the polygonal curves. Here, we consider the problem instance where the speed per segment is a constant within a specified range. We first describe a naive algorithm which solves the decision problem in O(n 3) time. Then, we develop a faster algorithm which is based on the naive one, but exhibits a running time of O(n 2 log n). Finally, we show that the exact Fréchet distance for this problem instance can be computed in O(n 2 log 2 n). 1