Computing the Fréchet distance with a retractable leash

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

Onderzoeksoutput: Boek/rapportRapportAcademic

68 Downloads (Pure)


All known algorithms for the Fr\'echet 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\'echet distance between polygonal curves in R^d under polyhedral distance functions, including L_1 and L_infty. We also get a (1+epsilon)-approximation of the Fr\'echet 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.
Originele taal-2Engels
Aantal pagina's13
StatusGepubliceerd - 2013

Publicatie series
Volume1306.5527 [cs.CG]

Citeer dit

Buchin, K., Buchin, M., Leusden, van, R., Meulemans, W., & Mulzer, W. (2013). Computing the Fréchet distance with a retractable leash. (; Vol. 1306.5527 [cs.CG]).