Fréchet distance with speed limits (Q621928)

The authors study generalizations of the Fréchet distance and algorithms for its calculation. This distance can be used to measure the similarity of two polygonal curves, and is defined as the maximum distance of two points which traverse the length of the two curves as constant speeds. The first two sections of this article present the necessary preliminaries to the Fréchet distance. This is followed by a presentation of the proposed algorithm and decision problem for the calculation of the Fréchet distance for any curve when limits are assumed on the speed of traversal. The fourth section then presents an improved version of the algorithm which has a running time of \(O(n^2\log^2{n})\).