Data Structures for Approximate Discrete Fréchet Distance
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917787067219968 |
|---|---|
| author | van der Hoog, Ivor Rotenberg, Eva Wong, Sampson |
| author_facet | van der Hoog, Ivor Rotenberg, Eva Wong, Sampson |
| contents | The Fréchet distance is a popular distance measure between curves $P$ and $Q$. Conditional lower bounds prohibit $(1 + \varepsilon)$-approximate Fréchet distance computations in strongly subquadratic time, even when preprocessing $P$ using any polynomial amount of time and space. As a consequence, the Fréchet distance has been studied under realistic input assumptions, for example, assuming both curves are $c$-packed.
In this paper, we study $c$-packed curves in Euclidean space $\mathbb R^d$ and in general geodesic metrics $\mathcal X$. In $\mathbb R^d$, we provide a nearly-linear time static algorithm for computing the $(1+\varepsilon)$-approximate continuous Fréchet distance between $c$-packed curves. Our algorithm has a linear dependence on the dimension $d$, as opposed to previous algorithms which have an exponential dependence on $d$.
In general geodesic metric spaces $\mathcal X$, little was previously known. We provide the first data structure, and thereby the first algorithm, under this model. Given a $c$-packed input curve $P$ with $n$ vertices, we preprocess it in $O(n \log n)$ time, so that given a query containing a constant $\varepsilon$ and a curve $Q$ with $m$ vertices, we can return a $(1+\varepsilon)$-approximation of the discrete Fréchet distance between $P$ and $Q$ in time polylogarithmic in $n$ and linear in $m$, $1/\varepsilon$, and the realism parameter $c$. Finally, we show several extensions to our data structure; to support dynamic extend/truncate updates on $P$, to answer map matching queries, and to answer Hausdorff distance queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_07124 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Data Structures for Approximate Discrete Fréchet Distance van der Hoog, Ivor Rotenberg, Eva Wong, Sampson Computational Geometry Data Structures and Algorithms The Fréchet distance is a popular distance measure between curves $P$ and $Q$. Conditional lower bounds prohibit $(1 + \varepsilon)$-approximate Fréchet distance computations in strongly subquadratic time, even when preprocessing $P$ using any polynomial amount of time and space. As a consequence, the Fréchet distance has been studied under realistic input assumptions, for example, assuming both curves are $c$-packed. In this paper, we study $c$-packed curves in Euclidean space $\mathbb R^d$ and in general geodesic metrics $\mathcal X$. In $\mathbb R^d$, we provide a nearly-linear time static algorithm for computing the $(1+\varepsilon)$-approximate continuous Fréchet distance between $c$-packed curves. Our algorithm has a linear dependence on the dimension $d$, as opposed to previous algorithms which have an exponential dependence on $d$. In general geodesic metric spaces $\mathcal X$, little was previously known. We provide the first data structure, and thereby the first algorithm, under this model. Given a $c$-packed input curve $P$ with $n$ vertices, we preprocess it in $O(n \log n)$ time, so that given a query containing a constant $\varepsilon$ and a curve $Q$ with $m$ vertices, we can return a $(1+\varepsilon)$-approximation of the discrete Fréchet distance between $P$ and $Q$ in time polylogarithmic in $n$ and linear in $m$, $1/\varepsilon$, and the realism parameter $c$. Finally, we show several extensions to our data structure; to support dynamic extend/truncate updates on $P$, to answer map matching queries, and to answer Hausdorff distance queries. |
| title | Data Structures for Approximate Discrete Fréchet Distance |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2212.07124 |