similarity of two curves. Many variants and extensions have been studied
since Alt and Godau introduced this measure to computational geometry in
1991. Their original algorithm to compute the Frechet distance of two
polygonal curves with n vertices has a runtime of O(n^2 log n). More
than 20 years later, the state of the art algorithms for most variants
still take time more than O(n^2 / log n), but no matching lower bounds
are known, not even under reasonable complexity theoretic assumptions.
To obtain a conditional lower bound, we assume the Strong Exponential
Time Hypothesis. Under this assumption we show that the Frechet distance
cannot be computed in strongly subquadratic time, i.e., in time
O(n^{2-delta}) for any delta > 0. This means that finding faster
algorithms for the Frechet distance is as hard as finding faster SAT
algorithms, and the existence of a strongly subquadratic algorithm can
be considered unlikely.