Static and Streaming Data Structures for Fréchet Distance Queries
Arnold Filtser, Omrit Filtser · Society for Industrial and Applied Mathematics eBooks · 2021
Given a curve P with points in ℝd in a streaming fashion, and parameters ∊ > 0 and k, we construct a distance oracle that uses space, and given a query curve Q with k points in ℝd, returns in O(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.