Approximating geodesics via random points

Erik Davis, Sunder Sethuraman

Published 2017-11-19Version 1

Given a `cost' functional $F$ on paths $\gamma$ in a domain $D\subset\mathbb{R}^d$, in the form $F(\gamma) = \int_0^1 f(\gamma(t),\dot\gamma(t))dt$, it is of interest to approximate its minimum cost and geodesic paths. Let $X_1,\ldots, 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|<\epsilon$, and the length scale $\epsilon=\epsilon_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.