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

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

2010-03-01

arxiv.org/abs/1003.0460v3

Computer Science

Computational Geometry

To appear in SoCG 10

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximating the Fréchet Distance for Realistic Curves in Near Linear Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating the Fréchet Distance for Realistic Curves in Near Linear Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the Fréchet Distance for Realistic Curves in Near Linear Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-662788