@inproceedings{932217e1d95e4296b2a9cd0828eb1282,

title = "Fr{\'e}chet distance for curves, revisited",

abstract = "We revisit the problem of computing the Fr{\'e}chet distance between polygonal curves, focusing on the discrete Fr{\'e}chet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: κ-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Fr{\'e}chet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.",

author = "Boris Aronov and Sariel Har-Peled and Christian Knauer and Yusu Wang and Carola Wenk",

year = "2006",

doi = "10.1007/11841036_8",

language = "English (US)",

isbn = "3540388753",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "52--63",

booktitle = "Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings",

note = "14th Annual European Symposium on Algorithms, ESA 2006 ; Conference date: 11-09-2006 Through 13-09-2006",

}