Approximating the Fréchet distance for realistic curves in near linear time

DOI10.1007/s00454-012-9402-zzbMath1243.68325OpenAlexW2570995828MaRDI QIDQ443909

Sariel Har-Peled, Carola Wenk, Anne Driemel

Publication date: 13 August 2012

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

Full work available at URL: https://doi.org/10.1007/s00454-012-9402-z

zbMATH Keywords

approximation algorithmsFréchet distancerealistic input models

Mathematics Subject Classification ID

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

Related Items

Computing the similarity between moving curves ⋮ Computing the Fréchet Distance Between Polygons with Holes ⋮ Computing the Fréchet distance with a retractable leash ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Fréchet Distance for Uncertain Curves ⋮ On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions ⋮ Unnamed Item ⋮ Computing the Fréchet distance between folded polygons ⋮ Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds ⋮ 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 ⋮ Approximating the Packedness of Polygonal Curves ⋮ Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance ⋮ Computing homotopic line simplification ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ Computing the Fréchet gap distance ⋮ Fast Fréchet Distance Between Curves with Long Edges ⋮ How to walk your dog in the mountains with no magic leash ⋮ Approximating the packedness of polygonal curves ⋮ Fast algorithms for approximate Fréchet matching queries in geometric trees ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry

Cites Work

• A note on the perimeter of fat objects
• Near-linear time approximation algorithms for curve simplification
• Improved bounds on the union complexity of fat objects
• Linear size binary space partitions for uncluttered scenes
• Realistic input models for geometric algorithms
• Comparison of distance measures for planar curves
• Detecting Commuting Patterns by Clustering Subtrajectories
• On Approximating the Depth and Related Problems
• The Computational Geometry of Comparing Shapes
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• Approximating the Fréchet distance for realistic curves in near linear time
• Fréchet Distance for Curves, Revisited