Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts

Details Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts

2011-07-08

arxiv.org/abs/1107.1720v3

Computer Science

Computational Geometry

Scientific paper

The similarity of two polygonal curves can be measured using the Fr\'echet distance. We introduce the notion of a more robust Fr\'echet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a constant factor approximation to the minimum Fr\'echet distance over all possible such shortcuts, in near linear time, if the curve is c-packed and the number of shortcuts is small. To facilitate the new algorithm we develop several new tools: (A) A data-structure for preprocessing a curve (not necessarily c-packed) that supports (1 + \eps)-approximate Fr\'echet distance queries between a subcurve (of the original curve) and a line segment. (B) A near linear time algorithm that computes a permutation of the vertices of a curve, such that any prefix of 2k-1 vertices of this permutation, form an optimal approximation (up to a constant factor) to the original curve compared to any polygonal curve with k vertices, for any k > 0. (C) A data-structure for preprocessing a curve that supports O(1)-approximate Fr\'echet distance queries between a subcurve and a query polygonal curve. The query time depends quadratically on the complexity of the query curve, and only (roughly) logarithmically on the complexity of the original curve. To our knowledge, these are the first data-structures to support these kind of queries efficiently.

Affiliated with

Also associated with

No associations

Rating

Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts 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 Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-674608