SETH says: weak Fréchet distance is faster, but only if it is continuous and in one dimension

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)
1 Downloads (Pure)

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 languageEnglish
Title of host publicationProc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages2887-2899
Number of pages13
ISBN (Electronic)978-1-61197-548-2
DOIs
Publication statusPublished - 1 Jan 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: 6 Jan 20199 Jan 2019

Conference

Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Country/TerritoryUnited States
CitySan Diego
Period6/01/199/01/19

Fingerprint

Dive into the research topics of 'SETH says: weak Fréchet distance is faster, but only if it is continuous and in one dimension'. Together they form a unique fingerprint.

Cite this