Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance

We propose κ-approximate nearest neighbor (ANN) data structures for n polygonal curves under the Fréchet distance in R^d, where κ ∈ {1 + ε, 3 + ε} and d ≥ 2. We assume that every input curve has at most m vertices, every query curve has at most k vertices, k ≪ m, and k is given for preprocessing. The query times are Õ(k(mn)^0.5+ε/ε^d + k(d/ε)^O(dk) for (1 + ε)-ANN and Õ(k(mn)^0.5+ε/ε^d) for (3 + ε)-ANN. The space and expected preprocessing time are Õ(k(mnd^d/ε^d)^O(k+1^/ε2)) in both cases. In two and three dimensions, we improve the query times to O(1/ε)^O(k) · Õ(k) for (1 + ε)-ANN and Õ(k) for (3 + ε)-ANN. The space and expected preprocessing time improve to O(mn/ε)^O(k) · Õ(k) in both cases. For ease of presentation, we treat factors in our bounds that depend purely on d as O(1). The hidden polylog factors in the big-Õ notation have powers dependent on d.