• Calendar

April 16, Wednesday
12:00 – 13:00

We show that for every $n$-point metric space $M$ there exists a spanning tree $T$ with unweighted diameter $O(log n)$ and weight $omega(T) = O! (log n) cdot omega(MST(M))$. Moreover, there is a designated point $rt$ such that for every point $v$, $dist_T(rt,v) le (1+epsilon) cdot dist_M(rt,v)$, for an arbitrarily small constant $epsilon > 0$. We extend this result, and provide a tradeoff between unweighted diameter and weight, and prove that this tradeoff is emph{tight up to constant factors} in the entire range of parameters. These results enable us to settle a long-standing open question in Computational Geometry. In STOC'95 Arya et al. devised a construction of Euclidean Spanners with unweighted diameter $O(log n)$ and weight $O(log n) cdot omega(MST(M))$. Ten years later in SODA'05 Agarwal et al. showed that this result is tight up to a factor of $O(log log n)$. We close this gap and show that the result of Arya et al. is tight up to constant factors. Joint work with Yefim Dinitz and Michael Elkin.