2015-08-01

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

## Publication

### Publication

*Computational Geometry , Volume 48 - Issue 6 p. 479- 494*

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.

Additional Metadata | |
---|---|

Keywords | Approximation algorithm, Fréchet distance, Geometric trees, Matching queries |

Persistent URL | dx.doi.org/10.1016/j.comgeo.2015.02.003 |

Journal | Computational Geometry |

Citation |
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 |