Approximate Nearest Neighbor for Polygonal Curves under Fréchet Distance
share
We propose κ-approximate nearest neighbor (ANN) data structures for n polygonal curves under the Fréchet distance in ℝ^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.
READ FULL TEXT