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 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 the curves in the given data set are large, 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.

Based on joint works with Arnold Filtser and Matya Katz.