Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2508.16875 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911118576844800 |
|---|---|
| author | Bikeev, Artur Kupavskii, Andrey Turevskii, Maxim |
| author_facet | Bikeev, Artur Kupavskii, Andrey Turevskii, Maxim |
| contents | For a given metric space $(P,ϕ)$, a tree cover of stretch $t$ is a collection of trees on $P$ such that edges $(x,y)$ of trees receive length $ϕ(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ϕ(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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16875 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tree covers of size $2$ for the Euclidean plane Bikeev, Artur Kupavskii, Andrey Turevskii, Maxim Computational Geometry For a given metric space $(P,ϕ)$, a tree cover of stretch $t$ is a collection of trees on $P$ such that edges $(x,y)$ of trees receive length $ϕ(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ϕ(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$. |
| title | Tree covers of size $2$ for the Euclidean plane |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2508.16875 |