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

•
• Overview
•
• Research
•
•
• View All
•

### abstract

• 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