TY - GEN
T1 - A Subquadratic nε-approximation for the Continuous Fréchet Distance.
AU - Horst, Thijs van der
AU - Kreveld, Marc J. van
AU - Ophelders, Tim
AU - Speckmann, Bettina
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2023
Y1 - 2023
N2 - 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 R^d in O(mn(log log n)²) 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 ́echet 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(α)-approximate algorithm that runs in O((n3/α2) log n) time for any α ∈ [√n, n], assuming m = n. In this paper, we improve this result with an O(α)-approximate algorithm that runs in O((n + mn/α) log³ n) time for any α ∈ [1, n], assuming m ≤ n andconstant dimension d.
AB - 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 R^d in O(mn(log log n)²) 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 ́echet 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(α)-approximate algorithm that runs in O((n3/α2) log n) time for any α ∈ [√n, n], assuming m = n. In this paper, we improve this result with an O(α)-approximate algorithm that runs in O((n + mn/α) log³ n) time for any α ∈ [1, n], assuming m ≤ n andconstant dimension d.
U2 - 10.1137/1.9781611977554.CH67
DO - 10.1137/1.9781611977554.CH67
M3 - Conference contribution
SP - 1759
EP - 1776
BT - Proc. 34th Annual Symposium on Discrete Algorithms (SODA)
T2 - Symposium on Discrete Algorithms (SODA23)
Y2 - 22 January 2023 through 25 January 2023
ER -