City Research Online

Computing the Fréchet Distance with a Retractable Leash

Buchin, K., Buchin, M., van Leusden, R., Meulemans, W. and Mulzer, W. (2016). Computing the Fréchet Distance with a Retractable Leash. Discrete and Computational Geometry, 56(2), pp. 315-336. doi: 10.1007/s00454-016-9800-8

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; 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échet distance between polygonal curves in (Formula presented.) under polyhedral distance functions (e.g., (Formula presented.) and (Formula presented.)). We also get a (Formula presented.)-approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed (Formula presented.). For the exact Euclidean case, our framework currently yields an algorithm with running time (Formula presented.). However, we conjecture that it may eventually lead to a faster exact algorithm.

Publication Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science > giCentre
URI: http://openaccess.city.ac.uk/id/eprint/15170
[img]
Preview
Text - Accepted Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (712kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login