An Optimal-Time Construction of Euclidean Sparse Spanners with Tiny Diameter

Shay Solomon

In STOC'95 \cite{ADMSS95} Arya et al.\ showed that for any set of $n$ points in ${\mathbb{R}}^d$, a $(1+\epsilon )$-spanner with diameter at most 2 (respectively, 3) and $O(n\log n)$ edges (…