A \((1+\varepsilon )\) -stretch tree cover of a metric space is a collection of trees, where every pair of points has a \((1+\varepsilon )\) -stretch path in one of the trees. The celebrated Dumbbell Theorem [Arya et al. STOC’95] states that any set of n points in d-dimensional Euclidean space admits a \((1+\varepsilon )\) -stretch tree cover with \(O_d(\varepsilon ^{-d} \cdot \log (1/\varepsilon ))\) trees, where the \(O_d\) notation suppresses terms that depend solely on the dimension d. The running time of their construction is \(O_d(n \log n \cdot \frac{\log (1/\varepsilon )}{\varepsilon ^{d}} + n \cdot \varepsilon ^{-2d})\) . Since the same point may occur in multiple levels of the tree, the maximum degree of a point in the tree cover may be as large as \(\Omega (\log \Phi )\) , where \(\Phi \) is the aspect ratio of the input point set. In this work we present a \((1+\varepsilon )\) -stretch tree cover with \(O_d(\varepsilon ^{-d+1} \cdot \log (1/\varepsilon ))\) trees, which is optimal (up to the \(\log (1/\varepsilon )\) factor). Moreover, the maximum degree of points in any tree is an absolute constant for any d. As a direct corollary, we obtain an optimal routing scheme in low-dimensional Euclidean spaces. We also present a \((1+\varepsilon )\) -stretch Steiner tree cover (that may use Steiner points) with \(O_d(\varepsilon ^{(-d+1)/{2}} \cdot \log (1/\varepsilon ))\) trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive \(O_d(n \log n)\) term; this improves over the running time underlying the Dumbbell Theorem.2
