Computing the Fréchet distance with a retractable leash

DOI10.1007/S00454-016-9800-8MaRDI QIDQ312142zbMATH OpenOpenAlexWikidataFDO

Authors Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans, Wolfgang Mulzer

Publication date 14 September 2016

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

approximationEuclidean distancepolyhedral distancesFréchet distance

Mathematics Subject Classification ID

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

Abstract: All known algorithms for the Fr'echet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fr'echet distance between polygonal curves in $R^d$ under polyhedral distance functions (e.g., $L_1$ and $L_{i}nfty$). We also get a $(1+varepsilon)$-approximation of the Fr'echet distance under the Euclidean metric, in quadratic time for any fixed $varepsilon>0$. For the exact Euclidean case, our framework currently yields an algorithm with running time $O(n^{2}lo{g}^{2}n)$. However, we conjecture that it may eventually lead to a faster exact algorithm.

Recommendations

• Computing the Fréchet distance with a retractable leash
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Computing the Fréchet gap distance
• Computing the Fréchet Gap Distance
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• Walking the dog fast in practice: algorithm engineering of the Fréchet distance
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES

Cites work

• scientific article; zbMATH DE number 1617248 (Why is no real title available?)
• scientific article; zbMATH DE number 1689042 (Why is no real title available?)
• Approximability of the discrete Fréchet distance
• Approximating the Fréchet distance for realistic curves in near linear time
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Detecting commuting patterns by clustering subtrajectories
• Faster kinetic heaps and their use in broadcast scheduling. (Extended abstract)
• Four Soviets walk the dog -- with an application to Alt's conjecture
• Geodesic Fréchet distance inside a simple polygon
• Maintenance of configurations in the plane
• Trekking in the alps without freezing or getting tired

Cited in

(14)

• scientific article; zbMATH DE number 7650283 (Why is no real title available?)
• The prefix Fréchet similarity
• Geodesic Fréchet distance inside a simple polygon
• Computing the Fréchet distance between simple polygons
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• Fréchet Distance for Curves, Revisited
• Fast Fréchet distance between curves with long edges
• Approximating the Fréchet distance for realistic curves in near linear time
• Computing the Fréchet distance with a retractable leash
• Fréchet distance with speed limits
• Computing the Fréchet distance between piecewise smooth curves
• Four Soviets walk the dog -- with an application to Alt's conjecture
• Walking the dog fast in practice: algorithm engineering of the Fréchet distance

This page was built for publication: Computing the Fréchet distance with a retractable leash

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q312142)