Jaywalking your dog: computing the Fréchet distance with shortcuts
From MaRDI portal
Publication:5396948
Abstract: 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 (3+eps)-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 either small or unbounded. 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 approximate Fr'echet distance queries between a subcurve and 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.
Recommendations
- Jaywalking your dog: computing the Fréchet distance with shortcuts
- The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
- The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
- Computing the Fréchet distance with shortcuts is NP-hard
- Similarity of polygonal curves in the presence of outliers
Cited in
(28)- scientific article; zbMATH DE number 7650283 (Why is no real title available?)
- Global Curve Simplification
- On computing the \(k\)-shortcut Fréchet distance
- Approximating the packedness of polygonal curves
- Tighter connections between Formula-SAT and shaving logs
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Fast Fréchet queries
- Fast algorithms for approximate Fréchet matching queries in geometric trees
- On the Chain Pair Simplification Problem
- Locality-sensitive hashing of curves
- Translation invariant Fréchet distance queries
- Approximating ( k,ℓ )-Median Clustering for Polygonal Curves
- Fréchet Distance for Uncertain Curves
- Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
- Fast Fréchet distance between curves with long edges
- Go with the flow: the direction-based Fréchet distance of polygonal curves
- On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions
- Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
- Computing the Fréchet distance with a retractable leash
- Computing the Fréchet gap distance
- Computing the Fréchet distance between folded polygons
- Jaywalking your dog: computing the Fréchet distance with shortcuts
- Universal approximate simplification under the discrete Fréchet distance
- Shortcut hulls: vertex-restricted outer simplifications of polygons
- Computing the Fréchet distance with shortcuts is NP-hard
- Approximating the Packedness of Polygonal Curves
- Approximate nearest neighbor for curves: simple, efficient, and deterministic
- scientific article; zbMATH DE number 7238975 (Why is no real title available?)
This page was built for publication: Jaywalking your dog: computing the Fréchet distance with shortcuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5396948)
