Fast Algorithms for Approximate Fréchet Matching Queries in Geometric Trees

Let T be a tree that is embedded in the plane and let ∆> 0 be a real number. The aim is to preprocess T into a data structure, such that for any query polygonal path Q, we can decide if T contains a path P whose Fréchet distance δF (P,Q) to Q is less than ∆. For any real number ε> 0, we present an efficient data structure that solves an approximate version of this problem for the case when T is c-packed and each of the edges of T and Q has length Ω(∆): If the data structure returns NO, then there is no such path P. If it returns YES, then δF (P,Q) ≤ (1 + ε) ∆ if Q is a line segment, and δF (P,Q) ≤ 3 ∆ otherwise.