Bringmann, Karl ;
Mulzer, Wolfgang
Approximability of the Discrete Fréchet Distance
Abstract
The Fréchet distance is a popular and widespread distance measure for point sequences and for curves. About two years ago, Agarwal et al [SIAM J. Comput. 2014] presented a new (mildly) subquadratic algorithm for the discrete version of the problem. This spawned a flurry of activity that has led to several new algorithms and lower bounds.
In this paper, we study the approximability of the discrete Fréchet distance. Building on a recent result by Bringmann [FOCS 2014], we present a new conditional lower bound that strongly subquadratic algorithms for the discrete Fréchet distance are unlikely to exist, even in the onedimensional case and even if the solution may be approximated up to a factor of 1.399.
This raises the question of how well we can approximate the Fréchet distance (of two given ddimensional point sequences of length n) in strongly subquadratic time. Previously, no general results were known. We present the first such algorithm by analysing the approximation ratio of a simple, lineartime greedy algorithm to be 2^Theta(n). Moreover, we design an alphaapproximation algorithm that runs in time O(n log n + n^2 / alpha), for any alpha in [1, n]. Hence, an n^epsilonapproximation of the Fréchet distance can be computed in strongly subquadratic time, for any epsilon > 0.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs:2015:5107,
author = {Karl Bringmann and Wolfgang Mulzer},
title = {{Approximability of the Discrete Fr{\'e}chet Distance}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {739753},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5107},
URN = {urn:nbn:de:0030drops51072},
doi = {10.4230/LIPIcs.SOCG.2015.739},
annote = {Keywords: Fr{\'e}chet distance, approximation, lower bounds, Strong Exponential Time Hypothesis}
}
12.06.2015
Keywords: 

Fréchet distance, approximation, lower bounds, Strong Exponential Time Hypothesis 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

12.06.2015 