Approximate Nearest Neighbor for Polygonal Curves under Fréchet Distance

Abstract

We propose $\kappa$-approximate nearest neighbor (ANN) data structures for $n$ polygonal curves under the Fréchet distance in ${\mathbb{R}}^d$, where $\kappa \in \{1+\epsilon ,3+\epsilon \}$ and $d\ge 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(mn{d}^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. 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-$\tilde{O}$ notation have powers dependent on $d$.

arXiv commentTo appear at ICALP 2023