Publication:1624582

DOI10.1007/978-3-642-33090-2_21zbMath1476.68279arXiv1206.6257OpenAlexW2892298325WikidataQ59782283 ScholiaQ59782283MaRDI QIDQ1624582

Maike Buchin, Wouter Meulemans, Kevin Buchin, Bettina Speckmann

Publication date: 16 November 2018

Published in: Computational Geometry, Algorithms – ESA 2012 (Search for Journal in Brave)

Abstract: The Frechet 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 Frechet distance a Frechet matching. There are often many different Frechet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Frechet matchings to "natural" matchings and to this end introduce locally correct Frechet 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 Frechet matching.

Full work available at URL: https://arxiv.org/abs/1206.6257

zbMATH Keywords

matchingsimilarityFréchet distancelocal correctness

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Computing the Fréchet distance with a retractable leash
• Fréchet distance with speed limits
• Approximating the integral Fréchet distance
• Locally correct Fréchet matchings
• New similarity measures between polylines with applications to morphing and polygon sweeping
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• The frechet distance revisited and extended
• Computing the Discrete Fréchet Distance in Subquadratic Time

Related Items (4)

Approximating the integral Fréchet distance ⋮ Locally correct Fréchet matchings ⋮ Computing the Fréchet distance with a retractable leash ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance

This page was built for publication: Locally correct Fréchet matchings