# 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.