MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

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

Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 22 May 2014
13:00
30 Minutes
E1 4
022
Saarbrücken

Abstract

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.

Contact

Karl Bringmann
--email hidden
passcode not visible
logged in users only

Karl Bringmann, 05/09/2014 17:53
Karl Bringmann, 05/09/2014 17:52 -- Created document.