2026-07-20T05:32:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19982 2024-06-06T06:21:14Z ddc:004 open_access

Optimal Euclidean Tree Covers Chang, Hsien-Chih Conroy, Jonathan Le, Hung Milenković, Lazar Solomon, Shay Than, Cuong Tree cover spanner Steiner point routing bounded-degree quadtree net-tree A (1+e)-stretch tree cover of a metric space is a collection of trees, where every pair of points has a (1+e)-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+e)-stretch tree cover with O_d(e^{-d} ⋅ log(1/e)) 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 ⋅ log(1/e)/e^d + n ⋅ e^{-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+e)-stretch tree cover with O_d(e^{-d+1} ⋅ log(1/e)) trees, which is optimal (up to the log(1/e) 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+e)-stretch Steiner tree cover (that may use Steiner points) with O_d(e^{(-d+1)/2} ⋅ log(1/e)) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hsien-Chih Chang and Jonathan Conroy and Hung Le and Lazar Milenković and Shay Solomon and Cuong Than 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.37 urn:nbn:de:0030-drops-199828 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.37 eng https://creativecommons.org/licenses/by/4.0/legalcode