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 $\mathrm{\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\mathrm{/}2k}\log \mathrm{\Delta })$ edges and runs in time $\tilde{O}({\tau }_{\mathsf{M}}\cdot k{n}^{1\mathrm{/}k}\log \mathrm{\Delta })$. (2) Any algorithm that learns at most $o(n^{1+1\mathrm{/}k}\mathrm{/}k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $\mathrm{\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 ${\mathrm{\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.