Computing the Fréchet distance with a retractable leash

K. Buchin, M. Buchin, R. Leusden, van, W. Meulemans, W. Mulzer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
62 Downloads (Pure)


All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; then they use this oracle to find the optimum among a finite set of critical values. We present a novel approach that avoids the detour through the decision version. We demonstrate its strength by presenting a quadratic time algorithm for the Fréchet distance between polygonal curves in R^d under polyhedral distance functions, including L_1 and L_infinity. We also get a (1+eps)-approximation of the Fréchet distance under the Euclidean metric. For the exact Euclidean case, our framework currently gives an algorithm with running time O(n^2 log^2 n). However, we conjecture that it may eventually lead to a faster exact algorithm.
Original languageEnglish
Title of host publication21st Annual European Symposium on Algorithms (ESA)
EditorsH.L. Bodlaender, G.F. Italiano
Place of PublicationBerlin
ISBN (Print)978-3-642-40449-8
Publication statusPublished - 2013
Event21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France
Duration: 2 Sep 20134 Sep 2013
Conference number: 21st

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference21st Annual European Symposium on Algorithms (ESA 2013)
Abbreviated titleESA 2013
CitySophia Antipolis
Internet address

Cite this