Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
From MaRDI portal
Publication:5370572
DOI10.1142/S0218195917600056zbMath1372.68253OpenAlexW2755486922MaRDI QIDQ5370572
Karl Bringmann, Marvin Künnemann
Publication date: 20 October 2017
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195917600056
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (5)
Translation invariant Fréchet distance queries ⋮ Approximating the Packedness of Polygonal Curves ⋮ Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance ⋮ Approximating the packedness of polygonal curves ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the Fréchet distance for realistic curves in near linear time
- Fréchet distance with speed limits
- Can we compute the similarity between surfaces?
- Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
- Fractional cascading. I: A data structuring technique
- Comparison of distance measures for planar curves
- Fréchet Queries in Geometric Trees
- DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES
- The Computational Geometry of Comparing Shapes
- Approximate nearest neighbor algorithms for Frechet distance via product metrics
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Approximate Map Matching with respect to the Fréchet Distance
- Four Soviets Walk the Dog—with an Application to Alt's Conjecture
- Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts
- The frechet distance revisited and extended
- Fréchet Distance for Curves, Revisited
- Computing the Discrete Fréchet Distance in Subquadratic Time
This page was built for publication: Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
