Fast Geometric Spanners via Approximate Nearest Neighbor Search

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M}=([n],\mathsf{d})$ with aspect ratio $\Delta$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime ${\tau }_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k\in \mathbb{N}$, constructs an $O(ck)$-distortion spanner with $\tilde{O}(k{n}^{1+1/2k}\log \Delta )$ edges and runs in time $\tilde{O}({\tau }_{\mathsf{M}}\cdot k{n}^{1/k}\log \Delta )$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $\Omega (ck)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance ${\mathsf{W}}_q$, for all $q>1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in ${\ell }_p$ spaces, for $p>2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and ${\mathsf{W}}_q$ distance approximation over these metric spaces.