Geodesics and Spanning Trees for Euclidean First-Passage Percolation

Abstract

The metric $D_{\alpha }(q,q^{\prime })$ on the set $Q$ of particle locations of a homogeneous Poisson process on $R^d$, defined as the infimum of $({\sum }_i|q_i-q_{i+1}{|}^{\alpha }{)}^{1/\alpha }$ over sequences in $Q$ starting with $q$ and ending with $q^{\prime }$ (where $|.|$ denotes Euclidean distance) has nontrivial geodesics when $\alpha >1$. The cases $1<\alpha <\infty$ are the Euclidean first-passage percolation (FPP) models introduced earlier by the authors while the geodesics in the case $\alpha =\infty$ are exactly the paths from the Euclidean minimal spanning trees/forests of Aldous and Steele. We compare and contrast results and conjectures for these two situations. New results for $1<\alpha <\infty$ (and any $d$) include inequalities on the fluctuation exponents for the metric ($\chi \le 1/2$) and for the geodesics ($\xi \le 3/4$) in strong enough versions to yield conclusions not yet obtained for lattice FPP: almost surely, every semi-infinite geodesic has an asymptotic direction and every direction has a semi-infinite geodesic (from every $q$). For $d=2$ and $2le\alpha <\infty$, further results follow concerning spanning trees of semi-infinite geodesics and related random surfaces.

63 pages, one figure; to appear in Ann. Probability