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

Computational Geometry