Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds

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

zbMATH Keywords

approximation algorithmFréchet distancecurve similarityrealistic curves

Mathematics Subject Classification ID

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