Name
Abstract | ||
|---|---|---|
Back in 1995, Alt and Godau gave an efficient algorithm for deciding whether a given curve resembles some part of a larger curve under a fixed Fréchet distance, achieving a running time of O(nmlog(nm)), for n and m being the number of segments in the two curves, respectively. We improve this long-standing result by presenting an algorithm that solves this decision problem in O(nm) time. Our solution is based on constructing a simple data structure which we call free-space map. Using this data structure, we obtain improved algorithms for several variants of the Fréchet distance problem, including the Fréchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the case when the map is a directed acyclic graph. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-013-9758-3 | european symposium on algorithms |
Keywords | DocType | Volume |
Fréchet distance,Partial curve matching,Closed curves,Free-space map | Journal | 69 |
Issue | ISSN | Citations |
3 | 0178-4617 | 7 |
PageRank | References | Authors |
0.44 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anil Maheshwari | 1 | 869 | 104.47 |
| Jörg-Rüdiger Sack | 2 | 1099 | 166.07 |
| Kaveh Shahbaz | 3 | 33 | 3.45 |
| Hamid Zarrabi-Zadeh | 4 | 111 | 13.63 |