Measuring the similarity of two curves or trajectories is an important task that arises in various applications. The Fréchet distance and its variants became very popular in the last few decades, and some variants were successfully applied to real data sets. The Fréchet distance between two curves can be computed in quadratic time using a simple dynamic programming algorithm. However, under SETH, no strongly subquadratic algorithms exist, even if the solution may be approximated up to a factor of 3. Therefore, in applications where there is a need to compute the distance to a single curve many times, or when the input curve is extremely large and quadratic running time is infeasible, a natural solution is to construct a data structure that allows fast distance queries. In this talk I will discuss approximate distance oracles and nearest neighbour search data structures under the discrete Fréchet distance. In addition, I will present an algorithm that constructs simplifications in the streaming model, an oracle for distance queries to a sub-curve, and introduce the zoom-in problem.
The talk is based on the following papers: