Covering the Euclidean Plane by a Pair of Trees
Abstract
A \(t\)-stretch tree cover of a metric space \(M = (X, \delta)\), 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+\epsilon)\)-stretch tree cover with \(O_\epsilon(1)\) trees. This result extends to any (constant) dimension and was also generalized for arbitrary doubling metrics by Bartal et al. [ICALP’19].
Fields of Study & Subjects
Computational Geometry and Mesh Generation
Geometric and Algebraic Topology
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 3472–3497
- Publication date
- 1 January 2026
- Language
- EN