$(1+\epsilon )$-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension

Jacobus Conradi, Anne Driemel, Benedikt Kolbe

We consider the $(1+\epsilon )$-Approximate Nearest Neighbour (ANN) Problem for polygonal curves in $d$-dimensional space under the Fréchet distance and ask to what extent known…