Locally correct Fréchet matchings

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

10 Citations (Scopus)
58 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication20th European Symposium on Algorithms (ESA)
EditorsL. Epstein, P. Ferragina
Place of PublicationBerlin
PublisherSpringer
Pages229-240
ISBN (Print)978-3-642-33089-6
DOIs
Publication statusPublished - 2012
Event20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia
Duration: 10 Sep 201212 Sep 2012
Conference number: 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

Publication series

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

Conference

Conference20th Annual European Symposium on Algorithms (ESA 2012)
Abbreviated titleESA 2012
CountrySlovenia
CityLjubljana
Period10/09/1212/09/12
Internet address

Cite this

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