Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

Details Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

2008-01-23

arxiv.org/abs/0801.3581v1

Computer Science

Computational Geometry

41 pages, 11 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183722