## 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-2 | Engels |
---|---|

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

Plaats van productie | New York |

Uitgeverij | Association for Computing Machinery, Inc |

Pagina's | 2887-2899 |

Aantal pagina's | 13 |

ISBN van elektronische versie | 978-1-61197-548-2 |

DOI's | |

Status | Gepubliceerd - 1 jan 2019 |

Evenement | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, Verenigde Staten van Amerika Duur: 6 jan 2019 → 9 jan 2019 |

### Congres

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

Land/Regio | Verenigde Staten van Amerika |

Stad | San Diego |

Periode | 6/01/19 → 9/01/19 |