Abstract
All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; then they use this oracle to find the optimum among a finite set of critical values. We present a novel approach that avoids the detour through the decision version. We demonstrate its strength by presenting a quadratic time algorithm for the Fréchet distance between polygonal curves in R^d under polyhedral distance functions, including L_1 and L_infinity. We also get a (1+eps)-approximation of the Fréchet distance under the Euclidean metric. For the exact Euclidean case, our framework currently gives an algorithm with running time O(n^2 log^2 n). However, we conjecture that it may eventually lead to a faster exact algorithm.
| Original language | English |
|---|---|
| Title of host publication | 21st Annual European Symposium on Algorithms (ESA) |
| Editors | H.L. Bodlaender, G.F. Italiano |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 241-252 |
| ISBN (Print) | 978-3-642-40449-8 |
| DOIs | |
| Publication status | Published - 2013 |
| Event | 21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France Duration: 2 Sept 2013 → 4 Sept 2013 Conference number: 21st http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 8125 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 21st Annual European Symposium on Algorithms (ESA 2013) |
|---|---|
| Abbreviated title | ESA 2013 |
| Country/Territory | France |
| City | Sophia Antipolis |
| Period | 2/09/13 → 4/09/13 |
| Internet address |