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

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