Approximating the Fréchet distance for realistic curves in near linear time
From MaRDI portal
Publication:443909
DOI10.1007/S00454-012-9402-ZzbMATH Open1243.68325OpenAlexW2570995828MaRDI QIDQ443909FDOQ443909
Authors: Anne Driemel, Sariel Har-Peled, Carola Wenk 
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
Recommendations
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Comparison of distance measures for planar curves
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Approximating the Fréchet distance for realistic curves in near linear time
- On Approximating the Depth and Related Problems
- The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
- Improved bounds on the union complexity of fat objects
- Realistic input models for geometric algorithms
- Linear size binary space partitions for uncluttered scenes
- Detecting Commuting Patterns by Clustering Subtrajectories
- The Computational Geometry of Comparing Shapes
- Fréchet Distance for Curves, Revisited
- A note on the perimeter of fat objects
- Near-linear time approximation algorithms for curve simplification
Cited In (31)
- Bounding and estimating the Hausdorff distance between real space algebraic curves
- Approximating the Fréchet distance for realistic curves in near linear time
- Approximating the integral Fréchet distance
- Tighter connections between Formula-SAT and shaving logs
- Approximating the packedness of polygonal curves
- When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
- Fréchet queries in geometric trees
- \((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Fast algorithms for approximate Fréchet matching queries in geometric trees
- Approximating the \(\lambda \)-low-density value
- Probabilistic embeddings of the Fréchet distance
- Fréchet Distance for Uncertain Curves
- Computing homotopic line simplification
- Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
- Fast Fréchet distance between curves with long edges
- Computing the Fréchet distance between uncertain curves in one dimension
- On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions
- How to walk your dog in the mountains with no magic leash
- Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
- Computing the Fréchet distance between uncertain curves in one dimension
- Computing the Fréchet gap distance
- Computing the Fréchet distance with a retractable leash
- Title not available (Why is that?)
- Computing the Fréchet distance between folded polygons
- Computing the Fréchet distance between polygons with holes
- SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
- Approximating the Packedness of Polygonal Curves
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance
This page was built for publication: Approximating the Fréchet distance for realistic curves in near linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443909)
