Faster Fréchet Distance under Transformations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915115927863296 |
|---|---|
| author | Buchin, Kevin Buchin, Maike Huang, Zijin Nusser, André Wong, Sampson |
| author_facet | Buchin, Kevin Buchin, Maike Huang, Zijin Nusser, André Wong, Sampson |
| contents | We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves $π$ and $σ$ of total complexity $n$ and a threshold $δ\geq 0$, we present an $\tilde{\mathcal{O}}(n^{7 + \frac{1}{3}})$ time algorithm to determine whether there exists a translation $t \in \mathbb{R}^2$ such that the Fréchet distance between $π$ and $σ+ t$ is at most $δ$. This improves on the previous best result, which is an $\mathcal{O}(n^8)$ time algorithm.
We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class $\mathcal T$ of rationally parametrized transformations with $k$ degrees of freedom, we show that one can determine whether there is a transformation $τ\in \mathcal T$ such that the Fréchet distance between $π$ and $τ(σ)$ is at most $δ$ in $\tilde{\mathcal{O}}(n^{3k+\frac{4}{3}})$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12814 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Fréchet Distance under Transformations Buchin, Kevin Buchin, Maike Huang, Zijin Nusser, André Wong, Sampson Computational Geometry We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves $π$ and $σ$ of total complexity $n$ and a threshold $δ\geq 0$, we present an $\tilde{\mathcal{O}}(n^{7 + \frac{1}{3}})$ time algorithm to determine whether there exists a translation $t \in \mathbb{R}^2$ such that the Fréchet distance between $π$ and $σ+ t$ is at most $δ$. This improves on the previous best result, which is an $\mathcal{O}(n^8)$ time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class $\mathcal T$ of rationally parametrized transformations with $k$ degrees of freedom, we show that one can determine whether there is a transformation $τ\in \mathcal T$ such that the Fréchet distance between $π$ and $τ(σ)$ is at most $δ$ in $\tilde{\mathcal{O}}(n^{3k+\frac{4}{3}})$ time. |
| title | Faster Fréchet Distance under Transformations |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2501.12814 |