# Approximating geodesics via random points

arXiv: https://arxiv.org/abs/1711.06952 · HTML: https://mlsanity.com/paper/1711.06952/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2017.

## Built on by (most cited first, 6 of 6)

- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [On convex decision regions in deep network representations](https://mlsanity.com/paper/2305.17154/) (2023)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [Entropic Optimal Transport in Random Graphs](https://mlsanity.com/paper/2201.03949/) (2022)
- [(Deep) Generative Geodesics](https://mlsanity.com/paper/2407.11244/) (2024)
- [Particle Filter Bridge Interpolation](https://mlsanity.com/paper/2103.14963/) (2021)

## Abstract (arXiv)

Given a `cost' functional F on paths γ in a domain Dsubsetℝd, in the form F(γ) = int01 f(γ(t),dotγ(t))dt, it is of interest to approximate its minimum cost and geodesic paths. Let X1,ldots, Xn be points drawn independently from D according to a distribution with a density. Form a random geometric graph on the points where Xi and Xj are connected when 0<|Xi - Xj|<ε, 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.