Tree covers of size $2$ for the Euclidean plane
By: Artur Bikeev, Andrey Kupavskii, Maxim Turevskii
Potential Business Impact:
Makes maps with fewer trees, faster travel.
For a given metric space $(P,\phi)$, a tree cover of stretch $t$ is a collection of trees on $P$ such that edges $(x,y)$ of trees receive length $\phi(x,y)$, and such that for any pair of points $u,v\in P$ there is a tree $T$ in the collection such that the induced graph distance in $T$ between $u$ and $v$ is at most $t\phi(u,v).$ In this paper, we show that, for any set of points $P$ on the Euclidean plane, there is a tree cover consisting of two trees and with stretch $O(1).$ Although the problem in higher dimensions remains elusive, we manage to prove that for a slightly stronger variant of a tree cover problem we must have at least $(d+1)/2$ trees in any constant stretch tree cover in $\mathbb R^d$.
Similar Papers
Covering the Euclidean Plane by a Pair of Trees
Computational Geometry
Makes finding paths in maps easier with two trees.
Spanning and Metric Tree Covers Parameterized by Treewidth
Data Structures and Algorithms
Finds shorter paths in complex networks.
Lower Bounds on Tree Covers
Data Structures and Algorithms
Makes maps easier to use with fewer roads.