Fast algorithms for approximate Fréchet matching queries in geometric trees
Let T be a tree in <sup>Rd</sup> and let Δ>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 <sup>δF</sup>(Q,P) to Q is at most Δ. 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 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 <sup>δF</sup>(Q,P)≤(1+ε)Δ if Q is a line segment, and b<sup>F</sup>(Q,P)≤3(1+ε)Δ otherwise.
|Keywords||Approximation algorithm, Fréchet distance, Geometric trees, Matching queries|
Gudmundsson, J. (Joachim), & Smid, M. (2015). Fast algorithms for approximate Fréchet matching queries in geometric trees. Computational Geometry, 48(6), 479–494. doi:10.1016/j.comgeo.2015.02.003