Approximating the Fréchet distance for realistic curves in near linear time
From MaRDI portal
Publication:443909
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
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
