Computing the Discrete Fréchet Distance in Subquadratic Time

DOI10.1137/130920526zbMath1297.68226arXiv1204.5333OpenAlexW2568308068MaRDI QIDQ5494924

Rinat Ben-Avraham, Haim Kaplan, Micha Sharir, Pankaj K. Agarwal

Publication date: 30 July 2014

Published in: SIAM Journal on Computing, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Fréchet distancesimilarity of curvesdynamic programming acceleration

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Formal languages and automata (68Q45) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (26)

Locally correct Fréchet matchings ⋮ Computing the Fréchet Distance Between Polygons with Holes ⋮ Following a curve with the discrete Fréchet distance ⋮ On the Chain Pair Simplification Problem ⋮ An improved approximation algorithm for the discrete Fréchet distance ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Gromov-Fréchet distance between curves ⋮ Fréchet Distance for Uncertain Curves ⋮ Discrete Fréchet distance for closed curves ⋮ Unnamed Item ⋮ Computing the Fréchet distance between folded polygons ⋮ Universal approximate simplification under the discrete Fréchet distance ⋮ Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds ⋮ Unnamed Item ⋮ When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ Computing the Fréchet gap distance ⋮ Fréchet distance between a line and avatar point set ⋮ Fast Fréchet Distance Between Curves with Long Edges ⋮ Unnamed Item ⋮ Fréchet distance between two point sets ⋮ Weighted minimum backward Fréchet distance ⋮ Fast algorithms for approximate Fréchet matching queries in geometric trees ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry

This page was built for publication: Computing the Discrete Fréchet Distance in Subquadratic Time