2025/03/04 by Pal, Dipranjan, Kumarjit Saha, Saha, Kumarjit
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2503.02594
openalex publication_date 2025/03/04 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
We study the ℓ∞ directed spanning forest(DSF), which is a directed forest with vertex set given by a homogeneous Poisson point process such that each Poisson point connects to the nearest Poisson point (in ℓ∞ distance) with a strictly larger y-coordinate. In this paper, we prove that the ℓ∞ DSF is connected and we find optimal estimates on the tail distribution of coalescing time of two ℓ∞ DSF paths. Similar estimates were earlier obtained in \citecoupier20212d for the ℓ2 (Euclidean) DSF and showed that when properly scaled, it converges in distribution to the Brownian web. The geometry of ℓ_∞ balls compel us to develop new argument.