Minimum Weight Euclidean $(1+\epsilon )$-Spanners

Abstract

Given a set $S$ of $n$ points in the plane and a parameter $\epsilon >0$, a Euclidean $(1+\epsilon )$-spanner is a geometric graph $G=(S,E)$ that contains, for all $p,q\in S$, a $pq$-path of weight at most $(1+\epsilon )\Vert pq\Vert$. We show that the minimum weight of a Euclidean $(1+\epsilon )$-spanner for $n$ points in the unit square $[0,1{]}^2$ is $O({\epsilon }^{-3/2}\sqrt{n})$, and this bound is the best possible. The upper bound is based on a new spanner algorithm in the plane. It improves upon the baseline $O({\epsilon }^{-2}\sqrt{n})$, obtained by combining a tight bound for the weight of a Euclidean minimum spanning tree (MST) on $n$ points in $[0,1{]}^2$, and a tight bound for the lightness of Euclidean $(1+\epsilon )$-spanners, which is the ratio of the spanner weight to the weight of the MST. Our result generalizes to Euclidean $d$-space for every constant dimension $d\in \mathbb{N}$: The minimum weight of a Euclidean $(1+\epsilon )$-spanner for $n$ points in the unit cube $[0,1{]}^d$ is $O_d({\epsilon }^{(1-d^2)/d}{n}^{(d-1)/d})$, and this bound is the best possible. For the $n\times n$ section of the integer lattice in the plane, we show that the minimum weight of a Euclidean $(1+\epsilon )$-spanner is between $\Omega ({\epsilon }^{-3/4}\cdot n^2)$ and $O({\epsilon }^{-1}\log ({\epsilon }^{-1})\cdot n^2)$. These bounds become $\Omega ({\epsilon }^{-3/4}\cdot \sqrt{n})$ and $O({\epsilon }^{-1}\log ({\epsilon }^{-1})\cdot \sqrt{n})$ when scaled to a grid of $n$ points in the unit square. In particular, this shows that the integer grid is \emph{not} an extremal configuration for minimum weight Euclidean $(1+\epsilon )$-spanners.

29 pages, 9 figures. An extended abstract appeared in the Proceedings of WG 2022