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 Citaties (Scopus)

Uittreksel

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.
TaalEngels
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

Buchin, K., Buchin, M., Leusden, van, R., Meulemans, W., & Mulzer, W. (2013). Computing the Fréchet distance with a retractable leash. In H. L. Bodlaender, & G. F. Italiano (editors), 21st Annual European Symposium on Algorithms (ESA) (blz. 241-252). (Lecture Notes in Computer Science; Vol. 8125). Berlin: Springer. DOI: 10.1007/978-3-642-40450-4_21
Buchin, K. ; Buchin, M. ; Leusden, van, R. ; Meulemans, W. ; Mulzer, W./ Computing the Fréchet distance with a retractable leash. 21st Annual European Symposium on Algorithms (ESA). redacteur / H.L. Bodlaender ; G.F. Italiano. Berlin : Springer, 2013. blz. 241-252 (Lecture Notes in Computer Science).
@inproceedings{f9f24aee4ba044d1807647223622a015,
title = "Computing the Fr{\'e}chet distance with a retractable leash",
abstract = "All known algorithms for the Fr{\'e}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{\'e}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{\'e}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.",
author = "K. Buchin and M. Buchin and {Leusden, van}, R. and W. Meulemans and W. Mulzer",
year = "2013",
doi = "10.1007/978-3-642-40450-4_21",
language = "English",
isbn = "978-3-642-40449-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "241--252",
editor = "H.L. Bodlaender and G.F. Italiano",
booktitle = "21st Annual European Symposium on Algorithms (ESA)",
address = "Germany",

}

Buchin, K, Buchin, M, Leusden, van, R, Meulemans, W & Mulzer, W 2013, Computing the Fréchet distance with a retractable leash. in HL Bodlaender & GF Italiano (redactie), 21st Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 8125, Springer, Berlin, blz. 241-252, Sophia Antipolis, Frankrijk, 2/09/13. DOI: 10.1007/978-3-642-40450-4_21

Computing the Fréchet distance with a retractable leash. / Buchin, K.; Buchin, M.; Leusden, van, R.; Meulemans, W.; Mulzer, W.

21st Annual European Symposium on Algorithms (ESA). redactie / H.L. Bodlaender; G.F. Italiano. Berlin : Springer, 2013. blz. 241-252 (Lecture Notes in Computer Science; Vol. 8125).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

TY - GEN

T1 - Computing the Fréchet distance with a retractable leash

AU - Buchin,K.

AU - Buchin,M.

AU - Leusden, van,R.

AU - Meulemans,W.

AU - Mulzer,W.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-40450-4_21

DO - 10.1007/978-3-642-40450-4_21

M3 - Conference contribution

SN - 978-3-642-40449-8

T3 - Lecture Notes in Computer Science

SP - 241

EP - 252

BT - 21st Annual European Symposium on Algorithms (ESA)

PB - Springer

CY - Berlin

ER -

Buchin K, Buchin M, Leusden, van R, Meulemans W, Mulzer W. Computing the Fréchet distance with a retractable leash. In Bodlaender HL, Italiano GF, redacteurs, 21st Annual European Symposium on Algorithms (ESA). Berlin: Springer. 2013. blz. 241-252. (Lecture Notes in Computer Science). Beschikbaar vanaf, DOI: 10.1007/978-3-642-40450-4_21