Unconstrained and Curvature-Constrained Shortest-Path Distances and their Approximation

06/28/2017

∙

by   Ery Arias-Castro, et al.

∙

0

∙

share

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 that Bernstein et al. (2000), developed in the context of manifold learning, and those of Karaman and Frazzoli (2011), developed in the context of robotics. We do the same with curvature-constrained shortest paths and their distances, establishing what we believe are the first approximation bounds for them.