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

Discrete and Computational Geometry. 2019. Vol. 62. No. 1. P. 1–28.

Arias-Castro E., Ле Г. Т.

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.

Ключевые слова: Curvature, shortest paths, Intrinsic distances, Motion planning, Approximation of distances, Neighborhood graph, Reach, Minimizing curves