The Radial Spanning Tree is straight in all dimensions

Tom Garcia-Sanchez · 2026

Read The Radial Spanning Tree is straight in all dimensions by Tom Garcia-Sanchez (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-08667.txt.

Introduction

Tom Garcia-Sanchez studies a random tree that grows from a single root point. Points fall at random in space. Each point links to the next point that sits close to the root. In this way a tree forms, with paths that run out from the root. The key ask is how straight those paths are.

He shows the tree is straight in all sizes of space, not just on a flat plane. Straight here means the paths do not bend far from a direct line. The proof adds to what we know about random shapes in space. A reader with a taste for chance and shape gets a neat, clean result. It also helps work on random nets that grow from one hub.

Catalog record

CREATORTom Garcia-Sanchez
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-08667

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Radial Spanning Tree is straight in all dimensions Tom Garcia-Sanchez Abstract The Radial Spanning Tree (RST) in dimension d ≥ 2 d\geq 2 is a random geometric graph constructed on a homogeneous Poisson point process 𝒩 \mathcal{N} in ℝ d \mathbb{R}^{d} augmented by the origin, with edges connecting each x ∈ 𝒩 x\in\mathcal{N} to the nearest point y ∈ 𝒩 ∪ { 0 } y\in\mathcal{N}\cup\{0\} that lies closer to 0 0 than x x , with respect to the Euclidean distance . By construction, it forms almost surely a tree rooted at 0 0 . The RST was introduced in 2007 by Baccelli and Bordenave, who investigated straightness , a deterministic property introduced by Howard and Newman in 2001, to derive information about the asymptotic directions of infinite branches . They proved that the RST is almost surely straight in dimension 2 2 , which directly implies that all infinite branches are asymptotically directed, every possibility is attained, and directions reached by multiple infinite branches form a dense subset. However, their approach relies crucially on planarity , preventing any straightforward extension to higher dimensions. In this paper, we close this gap by proving that the RST is almost surely straight in any dimension, thereby obtaining the same consequences for the behavior of infinite branches. Our approach resolves the key barriers in the study of the RST, notably those posed by the complex dependency structure combined with the radial nature of the model, and especially beyond the planar setting. It relies on tools developed for the analysis of the Directed Spanning Forest , a closely related model, including recent progress by the author in 2025. Specifically, a key contribution of this work is the construction of a suitable renewal-type decomposition of RST paths. Leveraging this decomposition together with classical concentration inequalities, we show that RST paths cannot deviate far from straight lines and derive straightness. Acknowledgments. The author warmly thanks his PhD advisors, David Coupier and Viet Chi Tran, for their continuous guidance and support throughout this work. This research was partly supported by the ANR project GrHyDy (ANR-20-CE40-0002), the CEFIPRA project Directed random networks and their scaling limits (No. 6901), the CNRS RT MAIAGES (Action 2179), and by a doctoral fellowship from ENS Paris. 1 Introduction In this paper, we study the Radial Spanning Tree (RST) in \mathbb{R}^{d} , for arbitrary fixed dimension d\geq 2 . The construction proceeds as follows. Consider an homogeneous Poisson point process \mathcal{N} of unit intensity in \mathbb{R}^{d} . Let \|\cdot\| denote the standard Euclidean norm of \mathbb{R}^{d} . If x\in\mathbb{R}^{d}\setminus\{0\} and X\subset\mathbb{R}^{d} are such that the infimum \inf_{\begin{subarray}{c}y\in X\cup\{0\}\\ \|y\|<\|x\|\end{subarray}}\|y-x\| is attained at a unique point, we denote such a minimizer by \Psi(x,X) . We set \Psi(0,X)\coloneqq 0 by convention. Since with probability one \mathcal{N} is locally finite and contains no nontrivial isosceles triangles, \Psi(x)\coloneqq\Psi(x,\mathcal{N}) is almost surely well defined for every x\in\mathcal{N} . The RST is then defined as the random geometric graph whose vertex set is \mathcal{N}\cup\{0\} and whose directed edges are given by \{(x,\Psi(x)):x\in\mathcal{N}\}. In words, each vertex x\in\mathcal{N} has a unique outgoing edge pointing to the nearest point in \mathcal{N}\cup\{0\} that lies closer to the origin. As \mathcal{N} is locally finite with probability one, the resulting graph is almost surely a tree rooted at 0 . Some simulations are presented in Figure 1 . Figure 1: Simulations of the RST within a finite ball around the origin, depicted as a dot. The picture on the left corresponds to d=2 , while the picture on the right corresponds to d=3 , with line color and thickness chosen to help visualizing the depth. Let us now outline the fundamental questions that arise in the study of infinite geometric trees. If T is a fixed deterministic tree in \mathbb{R}^{d} rooted at 0 , an infinite branch is defined as a backward path (u_{n})_{n\geq 0} starting at the root, that is a sequence of vertices such that (u_{n+1},u_{n}) is an edge of T for all n\geq 0 , and it is said to be asymptotically directed toward \xi\in\mathbb{S}^{d-1}\coloneqq\{\zeta\in\mathbb{R}^{d}:\|\zeta\|=1\} if \lim_{n\to\infty}\frac{u_{n}}{\|u_{n}\|}=\xi. This leads to several natural structural problems: How many infinite branches are there? Do they admit asymptotic directions? Which limits are possible? How many distinct infinite branches can share the same one? A crucial tool to address these questions is the notion of straightness , a property introduced by Howard and Newman [ HN01 ] in 2001, which we now define precisely. For any vertex u of T , denote by V_{u} the set of vertices in the sub-tree rooted at u . For any \xi\in\mathbb{S}^{d-1} and \theta\in\mathbb{R} , we define the cone pointing in direction \xi with aperture angle \theta as C[\xi,\theta]\coloneqq\{x\in\mathbb{R}^{d}:x\cdot\xi\geq\|x\|\cos\theta\}, where \cdot denotes the standard scalar product of \mathbb{R}^{d} . The tree T is said to be straight if there exists a function f:\mathbb{R}_{+}\to\mathbb{R}_{+} with \lim_{t\to\infty}f(t)=0 such that for all but finitely many vertices u\neq 0 of T , V_{u}\subset C\left[\frac{u}{\|u\|},f(\|u\|)\right]. In words, T is straight if the angular spread of its sub-trees vanishes as their root tends to infinity. The relevance of straightness stems from the following key proposition due to [ HN01 ] . Proposition 1.1 (Proposition 2.8 in [ HN01 ] ) . Assume that T is straight, each vertex has a finite degree, and the vertex set V_{0} of T is asymptotically omnidirectional, i.e. \left\{\frac{u}{\|u\|}:u\in V_{0},\penalty\ \|u\|\geq n\right\} is dense in \mathbb{S}^{d-1} for each n\geq 1 . Then, (i) Each infinite branch of T admits an asymptotic direction. (ii) For each \xi\in\mathbb{S}^{d-1} , there exists at least one infinite branch with asymptotic direction \xi . (iii) The set of \xi\in\mathbb{S}^{d-1} such that there exists more than one infinite branch with asymptotic direction \xi is dense in \mathbb{S}^{d-1} . In summary, under mild assumptions, establishing straightness provides extensive information about the infinite branches of a tree, and since such a property is deterministic, the ideal goal in the context of random geometric trees is to show that it holds almost surely. This is precisely what we achieve for the RST, stated as the main theorem of this work below. An illustration is provided in Figure 2 Theorem 1.2 . For every dimension d\geq 2 , the RST is almost surely straight, and Proposition 1.1 applies on an event of full probability. Figure 2: Simulation of the planar RST in a ball centered at the origin. Edges appear in light gray, with thickness decreasing with length. In red are highlighted some sub-trees exiting the displayed area, contained within translucent red cones pointing toward their sub-roots, with arbitrarily chosen apertures that appear to decrease to 0 with the distance to the origin, suggesting straightness. In black are highlighted some finite sub-trees remaining within the area, illustrating that RST sub-trees are not necessarily infinite. We now discuss the origin of the model as well as relevant existing results and related works. The RST was introduced in 2007 by Baccelli and Bordenave [ BB07 ] , who proved that it is almost surely straight in dimension 2 and, via Proposition 1.1 , derived detailed information about its infinite branches. These results were refined in 2013 by Baccelli, Coupier, and Tran [ BCT13 ] , who exploited planarity , i.e. the fact

Read the complete text