## Abstract

The metric D_{α}(q, q′) on the set Q of particle locations of a homogeneous Poisson process on ℝ^{d}, defined as the infimum of (∑_{i} |q_{i} - q_{i+1}|^{α})^{1/α} over sequences in Q starting with q and ending with q′ (where |·| denotes Euclidean distance) has nontrivial geodesics when α > 1. The cases 1 < α < ∞ are the Euclidean first-passage percolation (FPP) models introduced earlier by the authors, while the geodesics in the case α = ∞ 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 < α < ∞ (and any d) include inequalities on the fluctuation exponents for the metric (χ ≤ 1/2) and for the geodesics (ξ ≤ 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 ≤ α < ∞, further results follow concerning spanning trees of semiinfinite geodesics and related random surfaces.

Original language | English (US) |
---|---|

Pages (from-to) | 577-623 |

Number of pages | 47 |

Journal | Annals of Probability |

Volume | 29 |

Issue number | 2 |

DOIs | |

State | Published - Apr 2001 |

## Keywords

- Combinatorial optimization
- First-passage percolation
- Geodesic
- Minimal spanning tree
- Poisson process
- Random metric
- Random surface
- Shape theorem

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty