Unconstrained and Curvature-Constrained Shortest-Path Distances and Their Approximation
We study shortest paths and their distances on a subset of a Euclidean space, and their approximation by their equivalents in a neighborhood graph defined on a sample from that subset. In particular, we recover and extend the results of Bernstein et al. (Graph approximations to geodesics on embedded manifolds, Tech. Rep., Department of Psychology, Stanford University, 2000). We do the same with curvature-constrained shortest paths and their distances, establishing what we believe are the first approximation bounds for them.