Geodesics and spanning trees for Euclidean first-passage percolation

C. Douglas Howard, Charles M. Newman

Research output: Contribution to journalArticlepeer-review


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 |qi - qi+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 languageEnglish (US)
Pages (from-to)577-623
Number of pages47
JournalAnnals of Probability
Issue number2
StatePublished - Apr 2001


  • 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


Dive into the research topics of 'Geodesics and spanning trees for Euclidean first-passage percolation'. Together they form a unique fingerprint.

Cite this