Locally correct Fréchet matchings

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

10 Citaten (Scopus)
60 Downloads (Pure)

Samenvatting

The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N^3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N^2) algorithm to compute a locally correct discrete Fréchet matching.
Originele taal-2Engels
Titel20th European Symposium on Algorithms (ESA)
RedacteurenL. Epstein, P. Ferragina
Plaats van productieBerlin
UitgeverijSpringer
Pagina's229-240
ISBN van geprinte versie978-3-642-33089-6
DOI's
StatusGepubliceerd - 2012
Evenement20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenië
Duur: 10 sep 201212 sep 2012
Congresnummer: 20
http://link.springer.com/book/10.1007/978-3-642-33090-2
http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2012.html

Publicatie series

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

Congres

Congres20th Annual European Symposium on Algorithms (ESA 2012)
Verkorte titelESA 2012
LandSlovenië
StadLjubljana
Periode10/09/1212/09/12
Ander20th European Symposium on Algorithms
Internet adres

Citeer dit

Buchin, K., Buchin, M., Meulemans, W., & Speckmann, B. (2012). Locally correct Fréchet matchings. In L. Epstein, & P. Ferragina (editors), 20th European Symposium on Algorithms (ESA) (blz. 229-240). (Lecture Notes in Computer Science; Vol. 7501). Springer. https://doi.org/10.1007/978-3-642-33090-2_21