Data Structures for Proximity Searching under the Fréchet Distance

Anne Driemel, University of Bonn

Date and time: 2pm (New York time), Tuesday, November 2, 2021

Place: On Zoom here

We review different techniques for building a data structure that preprocesses a set of polygonal curves and answers proximity queries under the Fréchet distance. In particular, we consider the near-neighbor problem, where the query should return one curve that lies within a Fréchet distance $r$ to the query curve. In the approximate setting, the query radius $r$ can be relaxed by the query. We are interested in the preprocessing time, space and query time complexity that can be achieved when the data structure takes n polygonal curves, each with m vertices as input, and allows to query with polygonal curves of $k$ vertices. We first discuss exact data structures based on multi-level partition trees which can be used in the exact setting, but are very expensive with polylog-factors exponential in $k$. For the discrete Fréchet distance it is possible—by enumerating a discrete subset of the query space— to build a $(1+\epsilon)$-approximate data structure that uses space linear in $n$ and exponential in $k$ and query time only depending on $k$. We discuss some challenges that arise when translating this technique to the setting of the continuous Fréchet distance and discuss some recent advances in this direction.