Computing Fréchet distance with speed limits
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 in- stance 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(n3) time. Then, we develop a faster algorithm which is based on the naive one, but exhibits a running time of O(n2 log n). Finally, we show that the exact Fréchet distance for this problem instance can be computed in O(n2 log 2 n).
|Conference||21st Annual Canadian Conference on Computational Geometry, CCCG 2009|
Maheshwari, A, Sack, J.-R, & Shahbaz, K. (2009). Computing Fréchet distance with speed limits. Presented at the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009.