Computing the Fréchet distance with a retractable leash

DOI10.1007/S00454-016-9800-8zbMATH Open1355.68277arXiv1306.5527OpenAlexW2122538444WikidataQ59469027 ScholiaQ59469027MaRDI QIDQ312142FDOQ312142

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)

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.

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

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
• The frechet distance revisited and extended
• The frechet distance revisited and extended
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES

zbMATH Keywords

approximationEuclidean distancepolyhedral distancesFréchet distance

Mathematics Subject Classification ID

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

Cites Work

• Maintenance of configurations in the plane
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Trekking in the alps without freezing or getting tired
• Locally correct Fréchet matchings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster kinetic heaps and their use in broadcast scheduling. (Extended abstract)
• Approximability of the discrete Fréchet distance
• Detecting commuting patterns by clustering subtrajectories
• Geodesic Fréchet distance inside a simple polygon
• Approximating the Fréchet distance for realistic curves in near linear time
• Four Soviets Walk the Dog—with an Application to Alt's Conjecture
• The frechet distance revisited and extended

Cited In (11)

• Title not available (Why is that?)
• The prefix Fréchet similarity
• Geodesic Fréchet distance inside a simple polygon
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Computing the Fréchet distance between simple polygons
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• Fréchet Distance for Curves, Revisited
• Approximating the Fréchet distance for realistic curves in near linear time
• Locally correct Fréchet matchings
• Fréchet distance with speed limits
• Computing the Fréchet distance between piecewise smooth curves

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)