Static and Streaming Data Structures for Fréchet Distance Queries
share
Given a curve P with points in ℝ^d in a streaming fashion, and parameters ε>0 and k, we construct a distance oracle that uses O(1/ε)^kdlogε^-1 space, and given a query curve Q with k points in ℝ^d, returns in Õ(kd) time a 1+ε approximation of the discrete Fréchet distance between Q and P. In addition, we construct simplifications in the streaming model, oracle for distance queries to a sub-curve (in the static setting), and introduce the zoom-in problem. Our algorithms work in any dimension d, and therefore we generalize some useful tools and algorithms for curves under the discrete Fréchet distance to work efficiently in high dimensions.
READ FULL TEXT