SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension

Kevin Buchin, Tim Ophelders, Bettina Speckmann

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…