Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

2010/03/01 by Driemel, Anne, Har-Peled, Sariel, Wenk, Carola · 3 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1003.0460

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.

Cited by

• On computing the (exact) Fréchet distance with a frog
• The Measure of Deception: An Analysis of Data Forging in Machine Unlearning
• Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm

Related

• Approximating the Fréchet distance when only one curve is c-packed
• Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds
• Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm
• The Quick Dog Jumps the Log
• Data Structures for Approximate Discrete Fréchet Distance