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

DOI10.1145/1810959.1811019zbMATH Open1284.68295arXiv1003.0460OpenAlexW2030079560MaRDI QIDQ5405902FDOQ5405902

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)

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.

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

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

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)

Cited In (16)

• Bounding and estimating the Hausdorff distance between real space algebraic curves
• Approximating the integral Fréchet distance
• Approximating the packedness of polygonal curves
• Fréchet queries in geometric trees
• Fast Fréchet queries
• Fast algorithms for approximate Fréchet matching queries in geometric trees
• Approximating the Fréchet distance for realistic curves in near linear time
• The frechet distance revisited and extended
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• Title not available (Why is that?)
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• Title not available (Why is that?)
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Universal approximate simplification under the discrete Fréchet distance
• 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 Q5405902)