Shortest path through random points

DOI10.1214/15-AAP1162zbMATH Open1353.60028arXiv1202.0045MaRDI QIDQ350693FDOQ350693

Authors: Sung Jin Hwang, S. B. Damelin, Alfred O. III Hero 

Publication date: 9 December 2016

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1202.0045

Recommendations

• Shortest paths between shortest paths
• Shortest paths in random weighted graphs
• Shortest paths without a map
• Finding the shortest path in stochastic networks
• Stochastic shortest paths with recourse
• The expected length of a shortest path
• Shortest paths in arbitrary plane domains

zbMATH Keywords

almost sure convergenceRiemannian geometryshortest pathconformal metricpower-weighted graphrandom points

Mathematics Subject Classification ID

Methods of local Riemannian geometry (53B21) Strong limit theorems (60F15)

Cited In (11)

• A note on the length, measured along fixed orientations, of a path connecting any two points relative to their straight line distance
• Approximating geodesics via random points
• Convergence rates for estimators of geodesic distances and Fréchet expectations
• Entropic Optimal Transport on Random Graphs
• Approximating nearest neighbor distances
• Weighted lens depth: Some applications to supervised classification
• Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian
• Continuous approximation formulas for location problems
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Nonhomogeneous Euclidean first-passage percolation and distance learning
• Balancing geometry and density: path distances on high-dimensional data

This page was built for publication: Shortest path through random points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q350693)