Percolating paths through random points

David Aldous (1) , Maxim Krikun (2)

1 Department of Statistics [Berkeley]
2 IECN - Institut Élie Cartan de Nancy

We prove consistency of four different approaches to formalizing the idea of minimum average edge-length in a path linking some infinite subset of points of a Poisson process. The approaches are (i) shortest path from origin through some m distinct points; (ii) shortest average edge-length in paths across the diagonal of a large cube; (iii) shortest path through some specified proportion ? of points in a large cube; (iv) translation-invariant measures on paths in R^d which contain a proportion ? of the Poisson points. We develop basic properties of a normalized average length function c(?) and pose challenging open problem

Mots clés: Combinatorial optimization; continuum percolation; first passage percolation; Euclidean traveling salesman problem; Poisson process

Domaines: Probabilités [math.PR]

David Aldous, Maxim Krikun. Percolating paths through random points. ALEA : Latin American Journal of Probability and Mathematical Statistics, 2006, 1, pp.89--109. ⟨10.48550/arXiv.math/0509492⟩. ⟨hal-00140502⟩