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

DOI10.1145/1810959.1811019MaRDI QIDQ5405902zbMATH OpenOpenAlexFDO

Authors Anne Driemel, Carola Wenk, Sariel Har-Peled

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.0460

zbMATH Keywords

approximation algorithmsrealistic input modelsfrechet distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Curves in Euclidean and related spaces (53A04)

Abstract: We present simple and practical $(1+eps)$-approximation algorithm for the Frechet distance between curves. To analyze this algorithm we introduce a new realistic family of curves, $c$-packed curves, that is closed under simplification. We believe the notion of $c$-packed curves to be of independent interest. We show that our algorithm has near linear running time for $c$-packed curves, and show similar results for other input models.

Recommendations

• Approximating the Fréchet distance for realistic curves in near linear time
• Fréchet Distance for Curves, Revisited
• Fast Fréchet distance between curves with long edges
• A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance
• scientific article; zbMATH DE number 7051233
• Computing the Fréchet distance between piecewise smooth curves
• Approximately matching polygonal curves with respect to the Fréchet distance
• Discrete Fréchet distance for closed curves
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds

Cited in

(15)

• Approximating the packedness of polygonal curves
• Universal approximate simplification under the discrete Fréchet distance
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Bounding and estimating the Hausdorff distance between real space algebraic curves
• Approximating the Fréchet distance for realistic curves in near linear time
• A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance
• Approximating the integral Fréchet distance
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• scientific article; zbMATH DE number 7051233 (Why is no real title available?)
• Fréchet queries in geometric trees
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• \((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Fast Fréchet queries
• Fast algorithms for approximate Fréchet matching queries in geometric trees

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 Q5405902)