# Efficient Fréchet distance queries for segments

## Abstract

We study the problem of constructing a data structure that can store a two-dimensional polygonal curve $$P$$, such that for any query segment $$\overline{ab}$$ one can efficiently compute the Fréchet distance between $$P$$ and $$\overline{ab}$$. First we present a data structure of size $$O(n \log n)$$ that can compute the Fréchet distance between $$P$$ and a horizontal query segment $$\overline{ab}$$ in $$O(\log n)$$ time, where $$n$$ is the number of vertices of $$P$$. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment $$\overline{ab}$$ together with two points $$s, t \in P$$ (not necessarily vertices), and ask for the Fréchet distance between $$\overline{ab}$$ and the curve of $$P$$ in between $$s$$ and $$t$$. Using $$O(n\log^2n)$$ storage, such queries take $$O(\log^3 n)$$ time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an $$O(nk^{3+\eps}+n^2)$$ size data structure, where $$k \in [1,n]$$ is a parameter the user can choose, and $$\eps > 0$$ is an arbitrarily small constant, such that given any segment $$\overline{ab}$$ and two points $$s, t \in P$$ we can compute the Fréchet distance between $$\overline{ab}$$ and the curve of $$P$$ in between $$s$$ and $$t$$ in $$O((n/k)\log^2n+\log^4 n)$$ time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments.

We also present two applications of our data structure. First, we show that our data structure allows us to compute a local $$\delta$$-simplification (with respect to the Fréchet distance) of a polygonal curve in $$O(n^{5/2+\eps})$$ time, improving a previous $$O(n^3)$$ time algorithm. Second, we show that we can efficiently find a translation of an arbitrary query segment $$\overline{ab}$$ that minimizes the Fréchet distance with respect to a subcurve of $$P$$.

# Efficient Fréchet distance queries for segments

Proc. 30th European Symposium on Algorithms, 2022

@inproceedings{frechet_segmentqueries2022,
author = {Maike, Buchin and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and
I. Silveira, Rodrigo and Staals, Frank},
title = {Efficient Fréchet distance queries for segments},
booktitle = {Proc. 30th European Symposium on Algorithms},
year = {2022},
location = {Potsdam, Germany},
numpages = {14},
pages = {29:1--29:14},
keywords = {Computational Geometry, Data Structures, Fréchet distance},
category = {datastructures},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
doi = {10.4230/LIPIcs.ESA.2022.29},
url = {https://doi.org/10.4230/LIPIcs.ESA.2022.29},
}


# Improved space bounds for Fréchet distance queries

Abstr. 36th European Workshop on Computational Geometry (EuroCG), 2020

@article{frechet_datastructures_eurocg,
author = {Maike, Buchin and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and
I. Silveira, Rodrigo and Staals, Frank},
title = {Improved space bounds for Fréchet distance queries},
journal = {Abstr. 36th European Workshop on Computational Geometry (EuroCG)},
year = {2020},
location = {Wurzburg, Germany (online)},
numpages = {7},
category = {trajectories},