Abstract
We show by reduction from the Orthogonal Vectors problem that algorithms with strongly subquadratic running time cannot approximate the Fréchet distance between curves better than a factor 3 unless SETH fails. We show that similar reductions cannot achieve a lower bound with a factor better than 3. Our lower bound holds for the continuous, the discrete, and the weak discrete Fréchet distance even for curves in one dimension. Interestingly, the continuous weak Fréchet distance behaves differently. Our lower bound still holds for curves in two dimensions and higher. However, for curves in one dimension, we provide an exact algorithm to compute the weak Fréchet distance in linear time.
Original language | English |
---|---|
Title of host publication | Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
Place of Publication | New York |
Publisher | Association for Computing Machinery, Inc |
Pages | 2887-2899 |
Number of pages | 13 |
ISBN (Electronic) | 978-1-61197-548-2 |
DOIs | |
Publication status | Published - 1 Jan 2019 |
Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: 6 Jan 2019 → 9 Jan 2019 |
Conference
Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|
Country/Territory | United States |
City | San Diego |
Period | 6/01/19 → 9/01/19 |