Computing the Fréchet distance with a retractable leash

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)
54 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Titel21st Annual European Symposium on Algorithms (ESA)
RedacteurenH.L. Bodlaender, G.F. Italiano
Plaats van productieBerlin
UitgeverijSpringer
Pagina's241-252
ISBN van geprinte versie978-3-642-40449-8
DOI's
StatusGepubliceerd - 2013
Evenement21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, Frankrijk
Duur: 2 sep 20134 sep 2013
Congresnummer: 21st
http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Publicatie series

NaamLecture Notes in Computer Science
Volume8125
ISSN van geprinte versie0302-9743

Congres

Congres21st Annual European Symposium on Algorithms (ESA 2013)
Verkorte titelESA 2013
LandFrankrijk
StadSophia Antipolis
Periode2/09/134/09/13
Ander21st Annual European Symposium on Algorithms
Internet adres

Citeer dit