A Tight Lower Bound for Doubling Spanners

Any $n$-point set in the $d$-dimensional Euclidean space $\mathbb{R}^d$, for $d = O(1)$, admits a $(1+ε)$-spanner with $\tilde{O}(n \cdot ε^{-d+1})$ edges and lightness $\tilde{O}(ε^{-d})$, for any $ε> 0$. (The {lightness} is a normalized notion of weight, where we divide the spanner weight by the MST weight. The $\tilde{O}$ and $\tildeΩ$ notations hide $\texttt{polylog}(ε^{-1})$ terms.) Moreover, this result is tight: For any $2 \le d = O(1)$, there exists an $n$-point set in $\mathbb{R}^d$, for which any $(1+ε)$-spanner has $\tildeΩ(n \cdot ε^{-d+1})$ edges and lightness $\tildeΩ(n \cdot ε^{-d})$. The upper bounds for Euclidean spanners rely heavily on the spatial property of {cone partitioning} in $\mathbb{R}^d$, which does not seem to extend to the wider family of {doubling metrics}, i.e., metric spaces of constant {doubling dimension}. In doubling metrics, a {simple spanner construction from two decades ago, the {net-tree spanner}}, has $\tilde{O}(n \cdot ε^{-d})$ edges, and it could be transformed into a spanner of lightness $\tilde{O}(n \cdot ε^{-(d+1)})$ by pruning redundant edges. Despite a large body of work, it has remained an open question whether the superior Euclidean bounds of $\tilde{O}(n \cdot ε^{-d+1})$ edges and lightness $\tilde{O}(ε^{-d})$ could be achieved also in doubling metrics. We resolve this question in the negative by presenting a surprisingly simple and tight lower bound, which shows, in particular, that the net-tree spanner and its pruned version are both optimal.