Computing the Fr\'echet Distance with a Retractable Leash
| Autor: | Buchin, Kevin, Buchin, Maike, van Leusden, Rolf, Meulemans, Wouter, Mulzer, Wolfgang |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Discrete and Computational Geometry (DCG), 56(2), September 2016, pp. 315-336 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s00454-016-9800-8 |
| Popis: | All known algorithms for the Fr\'echet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fr\'echet distance between polygonal curves in $R^d$ under polyhedral distance functions (e.g., $L_1$ and $L_\infty$). We also get a $(1+\varepsilon)$-approximation of the Fr\'echet distance under the Euclidean metric, in quadratic time for any fixed $\varepsilon > 0$. For the exact Euclidean case, our framework currently yields an algorithm with running time $O(n^2 \log^2 n)$. However, we conjecture that it may eventually lead to a faster exact algorithm. Comment: 19 pages, 5 figures; a preliminary version appeared at ESA 2013 |
| Databáze: | arXiv |
| Externí odkaz: |
|