Locally correct Fréchet matchings

Research output: Contribution to journalArticleAcademicpeer-review

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.

LanguageEnglish
Pages1-18
Number of pages18
JournalComputational Geometry: Theory and Applications
Volume76
DOIs
StatePublished - 1 Jan 2019

Fingerprint

Curve
Monotone
Metric

Keywords

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

Cite this

@article{5a93ed185d514038b4ddf74a974fe081,
title = "Locally correct Fr{\'e}chet matchings",
abstract = "The Fr{\'e}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{\'e}chet distance a Fr{\'e}chet matching. There are often many different Fr{\'e}chet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fr{\'e}chet matchings to “natural” matchings and to this end introduce locally correct Fr{\'e}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{\'e}chet matching.",
keywords = "Fr{\'e}chet distance, Local correctness, Matching, Similarity",
author = "Kevin Buchin and Maike Buchin and Wouter Meulemans and Bettina Speckmann",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.comgeo.2018.09.002",
language = "English",
volume = "76",
pages = "1--18",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",

}

Locally correct Fréchet matchings. / Buchin, Kevin; Buchin, Maike; Meulemans, Wouter; Speckmann, Bettina.

In: Computational Geometry: Theory and Applications, Vol. 76, 01.01.2019, p. 1-18.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Locally correct Fréchet matchings

AU - Buchin,Kevin

AU - Buchin,Maike

AU - Meulemans,Wouter

AU - Speckmann,Bettina

PY - 2019/1/1

Y1 - 2019/1/1

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

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

KW - Fréchet distance

KW - Local correctness

KW - Matching

KW - Similarity

UR - http://www.scopus.com/inward/record.url?scp=85053664553&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2018.09.002

DO - 10.1016/j.comgeo.2018.09.002

M3 - Article

VL - 76

SP - 1

EP - 18

JO - Computational Geometry

T2 - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -