Let T be a tree that is embedded in the plane and let Δ, ε > 0 be real numbers. 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 Δ. 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 Ω(Δ) (not required if T is a path): If the data structure returns NO, then there is no such path P. ~(1/2)2(1 + ε)Δ if Q is a line segment, anIfditδFre(Ptu,rQn)s ≤YE3(S1, +thεe)nΔδFot(hPe,rQw)is≤e.
展开▼
