2024/03/26 by Chang, Hsien-Chih, Conroy, Jonathan, Le, Hung +3 · 7 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2403.17754
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 ⋅ log(1/ε)) trees, where the Od notation suppresses terms that depend solely on the dimension~d. The running time of their construction is Od(n log n ⋅ \fraclog(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 Ω(log Φ), where Φ is the aspect ratio of the input point set. In this work we present a (1+ε)-stretch tree cover with Od(ε-d+1 ⋅ log(1/ε)) trees, which is optimal (up to the log(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 ⋅ log(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 log n) term; this improves over the running time underlying the Dumbbell Theorem.