Shallow-low-light trees, and tight lower bounds for Euclidean spanners Conference Paper uri icon


  • We show that for every $ n $-point metric space $ M $ and positiveinteger $ k $, there exists a spanning tree $ T $ with unweighteddiameter $ O (k) $ and weight $ w (T)= O (k\cdot n^{1/k})\cdotw (MST (M)) $, and a spanning tree $ T'$ with weight $ w (T')= O (k)\cdotw (MST (M)) $ and unweighted diameter $ O (k\cdot n^{1/k}) $. Moreover, there is a designated point $ rt $ such that for every other point $ v $, both $ dist_T (rt, v) $ and $ dist_ {T'}(rt, v) $ are at most $(1+\epsilon)\cdot dist_M (rt, v) $, for an arbitrarily small constant $\epsilon≫ 0$. We prove that the above tradeoffs are\emph {tight up to constantfactors} in the entire range of parameters. Furthermore, our lowerbounds apply to a basic one-dimensional Euclidean space. Finally, our lower bounds for the particular case of unweighted diameter $ O (\log n) $ settle a long-standing open problem in ComputationalGeometry.

publication date

  • January 1, 2008