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

2017/06/28 by Arias-Castro, Ery, Gouic, Thibaut Le
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1706.09441

Abstract

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. (2000). We do the same with curvature-constrained shortest paths and their distances, establishing what we believe are the first approximation bounds for them.

Related

• Approximate Euclidean shortest paths in polygonal domains
• The Shortest-Path distance on graphons
• On Constrained and k Shortest Paths
• On the Number of Shortest Paths in Graphs
• On the Computational Complexity of Length- and Neighborhood-Constrained\n Path Problems