Shortest Path through Random Points

Abstract

Let $(M,g_1)$ be a complete $d$-dimensional Riemannian manifold for $d>1$. Let ${\mathcal{X}}_n$ be a set of $n$ sample points in $M$ drawn randomly from a smooth Lebesgue density $f$ supported in $M$. Let $x,y$ be two points in $M$. We prove that the normalized length of the power-weighted shortest path between $x,y$ through ${\mathcal{X}}_n$ converges almost surely to a constant multiple of the Riemannian distance between $x,y$ under the metric tensor $g_p=f^{2(1-p)/d}{g}_1$, where $p>1$ is the power parameter.