[2208.12721] A Subquadratic $n^ε$-approximation for the Continuous Fréchet Dista...
source link: https://arxiv.org/abs/2208.12721
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 26 Aug 2022]
A Subquadratic n^ε-approximation for the Continuous Fréchet Distance
The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with m and n vertices in \mathbb{R}^d in O(mn (\log \log n)^2) time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fréchet distance to within a factor 3 in strongly subquadratic time, even if d=1. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an O(\alpha)-approximate algorithm that runs in O((n^3 / \alpha^2) \log n) time for any \alpha \in [\sqrt{n}, n], assuming m = n. In this paper, we improve this result with an O(\alpha)-approximate algorithm that runs in O((n + mn / \alpha) \log^3 n) time for any \alpha \in [1, n], assuming m \leq n and constant dimension d.
| Comments: | 20 pages, 5 figures |
| Subjects: | Computational Geometry (cs.CG) |
| ACM classes: | F.2.2 |
| Cite as: | arXiv:2208.12721 [cs.CG] |
| (or arXiv:2208.12721v1 [cs.CG] for this version) | |
| https://doi.org/10.48550/arXiv.2208.12721 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK