Approximating geodesics via random points

Erik Davis, Sunder Sethuraman

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Given a cost functional F on paths γ in a domain D ⊂ R d , in the form F(γ) = 0 1 f (γ (t), γ (t))dt, it is of interest to approximate its minimum cost and geodesic paths. Let X 1 , . . ., X n be points drawn independently from D according to a distribution with a density. Form a random geometric graph on the points where X i and X j are connected when 0 < |X i − X j | < ε, and the length scale ε = ε n vanishes at a suitable rate. For a general class of functionals F, associated to Finsler and other distances on D, using a probabilistic form of Gamma convergence, we show that the minimum costs and geodesic paths, with respect to types of approximating discrete cost functionals, built from the random geometric graph, converge almost surely in various senses to those corresponding to the continuum cost F, as the number of sample points diverges. In particular, the geodesic path convergence shown appears to be among the first results of its kind.

Original languageEnglish (US)
Pages (from-to)1446-1486
Number of pages41
JournalAnnals of Applied Probability
Issue number3
StatePublished - Jan 1 2019


  • Consistency
  • Distance
  • Finsler
  • Gamma convergence
  • Geodesic
  • Random geometric graph
  • Scaling limit
  • Shortest path

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Approximating geodesics via random points'. Together they form a unique fingerprint.

Cite this