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.

13 pages