Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929761839742976 |
|---|---|
| author | Cheng, Siu-Wing Huang, Haoqiang Zhang, Shuo |
| author_facet | Cheng, Siu-Wing Huang, Haoqiang Zhang, Shuo |
| contents | Let $τ$ and $σ$ be two polygonal curves in $\mathbb{R}^d$ for any fixed $d$. Suppose that $τ$ and $σ$ have $n$ and $m$ vertices, respectively, and $m\le n$. While conditional lower bounds prevent approximating the Fréchet distance between $τ$ and $σ$ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of $n^c$ in strongly subquadratic time, for some constant $c\in(0,1)$. We present a randomized algorithm with running time $O(nm^{0.99}\log(n/\varepsilon))$ that approximates the Fréchet distance within a factor of $7+\varepsilon$, with a success probability at least $1-1/n^6$. We also adapt our techniques to develop a randomized algorithm that approximates the \emph{discrete} Fréchet distance within a factor of $7+\varepsilon$ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_12746 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant Approximation of Fréchet Distance in Strongly Subquadratic Time Cheng, Siu-Wing Huang, Haoqiang Zhang, Shuo Computational Geometry Data Structures and Algorithms Let $τ$ and $σ$ be two polygonal curves in $\mathbb{R}^d$ for any fixed $d$. Suppose that $τ$ and $σ$ have $n$ and $m$ vertices, respectively, and $m\le n$. While conditional lower bounds prevent approximating the Fréchet distance between $τ$ and $σ$ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of $n^c$ in strongly subquadratic time, for some constant $c\in(0,1)$. We present a randomized algorithm with running time $O(nm^{0.99}\log(n/\varepsilon))$ that approximates the Fréchet distance within a factor of $7+\varepsilon$, with a success probability at least $1-1/n^6$. We also adapt our techniques to develop a randomized algorithm that approximates the \emph{discrete} Fréchet distance within a factor of $7+\varepsilon$ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time. |
| title | Constant Approximation of Fréchet Distance in Strongly Subquadratic Time |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.12746 |