Towards Lower Bounds for Geometric Spanners in High Dimension

Abstract

We study the stretch--size tradeoff for geometric spanners in high-dimensional $\ell_p$ spaces. Our main contribution is a simple proof of a lower bound shown by Har-Peled, Indyk, and Sidiropoulos [SODA 2013]: Every $2$-hop $t$-spanner of the pointset $\{0,1\}^d$ under $\ell_2$ norm has at least $(2^d)^{1+\Omega(1/t^2)}$ edges. Our proof further extends this result to spanners with Steiner vertices. In addition, we establish a connection between bounded-hop spanners and general spanners, as follows. If every subset $Y$ of an $n$-point metric has a $t$-spanner with at most $\mu|Y|$ edges, then the metric has an $O(t)$-hop $O(t)$-spanner of size $O(n(\mu+\log n))$. Consequently, hop-restricted spanner lower bounds for a metric imply lower bounds without hop restriction for one of its subsets.