Optimal Euclidean Tree Covers

A (1+) -stretch tree cover of a metric space is a collection of trees, where every pair of points has a (1+) -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+) -stretch tree cover with Od (^-d (1/) ) trees, where the Od notation suppresses terms that depend solely on the dimension~d. The running time of their construction is Od (n n (1/) ^{d} + n ^-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 (), where is the aspect ratio of the input point set. In this work we present a (1+) -stretch tree cover with Od (^-d+1 (1/) ) trees, which is optimal (up to the (1/) 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+) -stretch Steiner tree cover (that may use Steiner points) with Od (^ (-d+1) /{2} (1/) ) 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 Od (n n) term; this improves over the running time underlying the Dumbbell Theorem.