Covering the Euclidean Plane by a Pair of Trees

Hung Le, Hung Le 0001, Lazar Milenkovic, Shay Solomon, Tianyi ZhangarXiv 2025 · DOI · arXiv

Abstract

This research addresses a fundamental challenge in computational geometry: efficiently covering the Euclidean plane with trees while minimizing distance distortion, known as "stretch." While previous methods required dozens of trees to achieve a constant stretch factor, this paper proves that just two trees are sufficient. By utilizing a quadtree-based Steiner tree construction and a strategic 45-degree rotation, the authors achieve a stretch factor of $\sqrt{26} \approx 5.1$. This result has significant implications for network design and compact routing.

Introduction

In computer science and network design, trees are favored for their simplicity and ease of routing. However, a single tree cannot preserve distances between all pairs of points in a plane. For instance, points on opposite sides of a circle may be physically close but far apart along the edges of any single spanning tree.

A $t$-stretch tree cover is a collection of trees where every pair of points in a set is connected by a path in at least one tree with a length at most $t$ times their direct Euclidean distance. The central question explored in this paper is: what is the absolute minimum number of trees required to achieve a constant stretch factor? This work resolves the question by demonstrating that two trees are enough.

The Two-Tree Construction

The authors propose a construction using Steiner trees—trees that can include auxiliary "helper" points to facilitate connections. The method relies on the recursive structure of quadtrees, where the plane is partitioned into four squares at each level.

Recursive quadtree-based Steiner tree construction showing the basic cross unit and its hierarchical expansion.

The first tree is a standard quadtree construction where internal nodes are the centers of the squares. The breakthrough comes with the second tree, which is a copy of the first, rotated by 45 degrees and inflated by a factor of $\sqrt{2}$. This specific geometric transformation ensures that "bad pairs"—points separated by major boundaries in the first tree—are guaranteed to be well-connected in the second.

Key Insights and Results

The 45-degree rotation is the "secret sauce" of the construction. It ensures that the boundaries of the second quadtree bisect the critical regions of the first, effectively capturing the pairs the first tree misses. This approach "breaks the level dependency" typically found in recursive geometric constructions, allowing for a tight stretch analysis level-by-level.

Global pattern of the two-tree cover and the directional logic behind the 45-degree rotation.

Major Findings:

  • Steiner Tree Cover: Two trees achieve a stretch factor of $\sqrt{26} \approx 5.1$. The authors prove this bound is tight for this specific construction.
  • Spanning Tree Cover: By applying a pruning algorithm to remove Steiner points, a two-tree spanning cover is achieved with a stretch factor of $4\sqrt{26} \approx 20.4$.
  • Compact Routing: The construction enables a routing scheme using only $(2 + o(1)) \log n$ bits of memory per node, a significant improvement over previous schemes that often required over $50 \log n$ bits.
  • Efficiency: The trees can be constructed in $O(n \log n)$ time, making the approach practical for large-scale point sets.

Conclusion

This work provides a surprisingly simple and efficient solution to a long-standing problem in computational geometry. By showing that two trees are sufficient to cover the plane with low stretch, the authors pave the way for more efficient network protocols and data structures. While the 2D case is now well-understood, extending this "rotate and inflate" logic to higher dimensions remains an open and challenging problem for future research.

Summary updated

Abstract

A {$t$-stretch tree cover} of a metric space $M = (X,δ)$, for a parameter $t \ge 1$, is a collection of trees such that every pair of points has a $t$-stretch path in one of the trees. Tree covers provide an important sketching tool that has found various applications over the years. The celebrated {Dumbbell Theorem} by Arya et al. [STOC'95] states that any set of points in the Euclidean plane admits a $(1+ε)$-stretch tree cover with $O_ε(1)$ trees. This result extends to any (constant) dimension and was also generalized for arbitrary doubling metrics by Bartal et al. [ICALP'19]. Although the number of trees provided by the Dumbbell Theorem is constant, this constant is not small, even for a stretch significantly larger than $1+ε$. At the other extreme, any single tree on the vertices of a regular $n$-polygon must incur a stretch of $Ω(n)$. Using known results of ultrametric embeddings, one can easily get a stretch of $\tilde{O}(\sqrt{n})$ using two trees. The question of whether a low stretch can be achieved using two trees has remained illusive, even in the Euclidean plane. In this work, we resolve this fundamental question in the affirmative by presenting a constant-stretch cover with a pair of trees, for any set of points in the Euclidean plane. Our main technical contribution is a {surprisingly simple} Steiner construction, for which we provide a {tight} stretch analysis of $\sqrt{26}$. The Steiner points can be easily pruned if one is willing to increase the stretch by a small constant. Moreover, we can bound the maximum degree of the construction by a constant. Our result thus provides a simple yet effective reduction tool -- for problems that concern approximate distances -- from the Euclidean plane to a pair of trees. To demonstrate the potential power of this tool, we present some applications [...]
BibTeX
@misc{le2025covering,
  author = {Hung Le and Hung Le and Lazar Milenkovic and Shay Solomon and Tianyi Zhang},
  title = {{Covering the Euclidean Plane by a Pair of Trees}},
  year = {2025},
  eprint = {2508.11507},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.11507},
}
Figure