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

Kevin Buchin; Tim Ophelders; Bettina Speckmann

doi:10.1137/1.9781611975482.179

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

Kevin Buchin, Tim Ophelders, Bettina Speckmann

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

34 Citations (Scopus)

6 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 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	https://doi.org/10.1137/1.9781611975482.179
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

Access to Document

10.1137/1.9781611975482.179

https://arxiv.org/pdf/1807.08699.pdf

Cite this

@inproceedings{d7baf4ab7a994b979a19cdcc1df670ef,

title = "SETH says: weak Fr{\'e}chet distance is faster, but only if it is continuous and in one dimension",

abstract = "We show by reduction from the Orthogonal Vectors problem that algorithms with strongly subquadratic running time cannot approximate the Fr{\'e}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{\'e}chet distance even for curves in one dimension. Interestingly, the continuous weak Fr{\'e}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{\'e}chet distance in linear time.",

author = "Kevin Buchin and Tim Ophelders and Bettina Speckmann",

year = "2019",

month = jan,

day = "1",

doi = "10.1137/1.9781611975482.179",

language = "English",

pages = "2887--2899",

booktitle = "Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 ; Conference date: 06-01-2019 Through 09-01-2019",

}

Buchin, K, Ophelders, T & Speckmann, B 2019, SETH says: weak Fréchet distance is faster, but only if it is continuous and in one dimension. in Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Association for Computing Machinery, Inc, New York, pp. 2887-2899, 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States, 6/01/19. https://doi.org/10.1137/1.9781611975482.179

SETH says: weak Fréchet distance is faster, but only if it is continuous and in one dimension. / Buchin, Kevin; Ophelders, Tim ; Speckmann, Bettina.
Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). New York: Association for Computing Machinery, Inc, 2019. p. 2887-2899.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Buchin, Kevin

AU - Ophelders, Tim

AU - Speckmann, Bettina

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85066960380&partnerID=8YFLogxK

UR - https://dl.acm.org/citation.cfm?id=3310614

U2 - 10.1137/1.9781611975482.179

DO - 10.1137/1.9781611975482.179

M3 - Conference contribution

AN - SCOPUS:85066960380

SP - 2887

EP - 2899

BT - Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

PB - Association for Computing Machinery, Inc

CY - New York

T2 - 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019

Y2 - 6 January 2019 through 9 January 2019

ER -

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

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this