Fast algorithms for approximate Fréchet matching queries in geometric trees

Let T   be a tree in RdRd and let Δ>0Δ>0 be a real number. The aim is to preprocess T into a data structure, such that for any polygonal query path Q, we can decide if T contains a path P   whose Fréchet distance δF(Q,P)δF(Q,P) to Q   is at most Δ. For any real number ε>0ε>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 query algorithm returns NO, then there is no such path P. If the query algorithm returns YES, then T contains a path P   for which δF(Q,P)≤(1+ε)ΔδF(Q,P)≤(1+ε)Δ if Q   is a line segment, and δF(Q,P)≤3(1+ε)ΔδF(Q,P)≤3(1+ε)Δ otherwise.