Abstract
We propose \(\kappa\)-approximate nearest neighbor (ANN) data structures for \(n\) polygonal curves under the Fr\'\{e\}chet distance in \(\mathbb\{R\}^d\), where \(\kappa \in \\{1+\epsilon,3+\epsilon\\}\) and \(d \geq 2\). We assume that every input curve has at most \(m\) vertices, every query curve has at most \(k\) vertices, \(k \ll m\), and \(k\) is given for preprocessing. The query times are \(\tilde\{O\}(k(mn)^\{0.5+\epsilon\}/\epsilon^d+ k(d/\epsilon)^\{O(dk)\})\) for \((1+\epsilon)\)-ANN and \(\tilde\{O\}(k(mn)^\{0.5+\epsilon\}/\epsilon^d)\) for \((3+\epsilon)\)-ANN. The space and expected preprocessing time are \(\tilde\{O\}(k(mnd^d/\epsilon^d)^\{O(k+1/\epsilon^2)\})\) in both cases. In two and three dimensions, we improve the query times to \(O(1/\epsilon)^\{O(k)\} \cdot \tilde\{O\}(k)\) for \((1+\epsilon)\)-ANN and \(\tilde\{O\}(k)\) for \((3+\epsilon)\)-ANN. The space and expected preprocessing time improve to \(O(mn/\epsilon)^\{O(k)\} \cdot \tilde\{O\}(k)\) in both cases.