Special Invited Paper: Geodesics And Spanning Tees For Euclidean First­Passage Percolaton

Howard, C. Douglas ; Newman, Charles M.

Ann. Probab., Tome 29 (2001) no. 1, p. 577-623 / Harvested from Project Euclid

Résumé

The metric $D_{\alpha}(q,q')$ on the set $Q$ of particle locations of a homogeneous Poisson process on $\mathbb{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'$ (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 semiinfinite geodesic has an asymptotic direction and every direction has a semiinfinite geodesic (from every $q$). For $d = 2$ and $2 \le \alpha < \infty$, further results follow concerning spanning trees of semiinfinite geodesics and related random surfaces.

Détail

Publié le : 2001-04-14
Classification:  first­passage percolation,  random metric,  minimal spanning tree,  geodesic,  combinatorial optimization,  shape theorem,  random surface,  Poisson process,  60K35,  60G55,  82D30,  60F10