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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
TitelSODA '19 Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's2887-2899
Aantal pagina's13
ISBN van elektronische versie978-1-61197-548-2
DOI's
StatusGepubliceerd - 1 jan 2019
Evenement30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, Verenigde Staten van Amerika
Duur: 6 jan 20199 jan 2019

Congres

Congres30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
LandVerenigde Staten van Amerika
StadSan Diego
Periode6/01/199/01/19

Vingerafdruk Duik in de onderzoeksthema's van 'Seth says: weak Fréchet distance is faster, but only if it is continuous and in one dimension'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    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 SODA '19 Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (blz. 2887-2899). Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611975482.179