The following paper has been presented at IWISC 2018 and has received the best paper award: J. Gudmundsson, M. Mirzanezhad, A. Mohades, C. Wenk. Fast Fréchet Distance for Curves with Long Edges. 3rd International Workshop on Interactive and Spatial Computing: 52-58, Richardson, TX, 2018.
Computing Fréchet distance between two curves takes roughly quadratic time. This paper shows that for curves with long edges the Fréchet distance computations become easier. Let P and Q be two polygonal curves in Rd with n and m vertices, respectively. Three main results are proven for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in O((n + m) log(n + m)) time, and (3) a linear-time sqrt(d)-approximation algorithm for approximating the Fréchet distance between two curves.