Abstract
The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N^3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N^2) algorithm to compute a locally correct discrete Fréchet matching.
| Original language | English |
|---|---|
| Title of host publication | 20th European Symposium on Algorithms (ESA) |
| Editors | L. Epstein, P. Ferragina |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 229-240 |
| ISBN (Print) | 978-3-642-33089-6 |
| DOIs | |
| Publication status | Published - 2012 |
| Event | 20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia Duration: 10 Sept 2012 → 12 Sept 2012 Conference number: 20 http://link.springer.com/book/10.1007/978-3-642-33090-2 http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2012.html |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 7501 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 20th Annual European Symposium on Algorithms (ESA 2012) |
|---|---|
| Abbreviated title | ESA 2012 |
| Country/Territory | Slovenia |
| City | Ljubljana |
| Period | 10/09/12 → 12/09/12 |
| Internet address |