Locally correct Fréchet matchings

Kevin Buchin, Maike Buchin, Wouter Meulemans (Corresponding author), Bettina Speckmann

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

Abstract

The Fréchet distance is a metric to compare two curves, which is based on monotone 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(N3log⁡N) algorithm to compute it, where N is the number of edges in both curves. We also present an O(N2) algorithm to compute a locally correct discrete Fréchet matching.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalComputational Geometry
Volume76
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • Fréchet distance
  • Local correctness
  • Matching
  • Similarity
  • Frechet distance

Fingerprint Dive into the research topics of 'Locally correct Fréchet matchings'. Together they form a unique fingerprint.

  • Cite this