Covering the Euclidean Plane by a Pair of Trees

A t-stretch tree cover of a metric space M = (X, δ), for a parameter t ≥ 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 Õ( √ 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 constantstretch 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 √ 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 for routing algorithms, including a constantstretch compact routing scheme when handshaking is allowed, on top of a pair of trees, in which the total memory usage is just (2 + o(1)) log n bits.