Faster Fréchet Distance Approximation through Truncated Smoothing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910933154004992 |
|---|---|
| author | van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina |
| author_facet | van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina |
| contents | The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of $n$ vertices takes roughly quadratic time, and conditional lower bounds suggest that approximating to within a factor $3$ cannot be done in strongly-subquadratic time, even in one dimension. Currently, the best approximation algorithms present trade-offs between approximation quality and running time. At SoCG 2021, Colombe and Fox presented an $O((n^3 / α^2) \log n)$-time $α$-approximate algorithm for curves in arbitrary dimensions, for any $α\in [\sqrt{n}, n]$. In this work, we give an $α$-approximate algorithm with a significantly faster running time of $O((n^2 / α) \log n)$, for any $α\in [1, n]$. In particular, we give the first strongly-subquadratic $n^\varepsilon$-approximation algorithm, for any constant $\varepsilon \in (0, 1/2]$. For curves in one dimension we further improve the running time to $O((n^2 / α^3) \log^2 n)$, for $α\in [1, n^{1/3}]$. Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to $O(n^2 / α)$ without making sacrifices in the asymptotic approximation factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14815 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Fréchet Distance Approximation through Truncated Smoothing van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina Computational Geometry F.2.2 The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of $n$ vertices takes roughly quadratic time, and conditional lower bounds suggest that approximating to within a factor $3$ cannot be done in strongly-subquadratic time, even in one dimension. Currently, the best approximation algorithms present trade-offs between approximation quality and running time. At SoCG 2021, Colombe and Fox presented an $O((n^3 / α^2) \log n)$-time $α$-approximate algorithm for curves in arbitrary dimensions, for any $α\in [\sqrt{n}, n]$. In this work, we give an $α$-approximate algorithm with a significantly faster running time of $O((n^2 / α) \log n)$, for any $α\in [1, n]$. In particular, we give the first strongly-subquadratic $n^\varepsilon$-approximation algorithm, for any constant $\varepsilon \in (0, 1/2]$. For curves in one dimension we further improve the running time to $O((n^2 / α^3) \log^2 n)$, for $α\in [1, n^{1/3}]$. Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to $O(n^2 / α)$ without making sacrifices in the asymptotic approximation factor. |
| title | Faster Fréchet Distance Approximation through Truncated Smoothing |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2401.14815 |