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.
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.
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