Efficient trajectory queries under the Fréchet distance (GIS Cup)
Kevin Buchin, Yago Díez, Tom van Diggelen, Wouter Meulemans · 2017
Consider a set P of trajectories (polygonal lines in R2), and a query given by a trajectory Q and a threshold ϵ > 0. To answer the query we wish to find all trajectories P ∈ P such that δF(P, Q) ≤ ϵ, where δF denotes the Fréchet distance. We present an approach to efficiently answer a large number of queries for the same set P. Key ingredients are (a) precomputing a spatial hash that allows us to quickly find trajectories that have endpoints near Q; (b) precomputing simplifications on all trajectories in P; (c) using the simplifications and optimizations of the decision algorithm to efficiently decide δF(P, Q) ≤ ϵ for most P ∈ P.