MADALGO seminar

MADALGO theory seminar: Karl Bringman, Max-Plank-Institut für Informatik

2014.06.24 | Trine Ji Holmgaard Jensen

Date Wed 02 Jul
Time 14:15 15:00

Theory seminar

Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails

Speaker: Karl Bringman, Max-Planck-Institut für Informatik


Time: Wednesday, July 2 at 14:15 to 15:00

Location: Nygaard 395



The Frechet distance is a well-studied and very popular measure of 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.


Host: Kasper Green Larsen