APPROXIMATING GEODESICS VIA RANDOM POINTS

• 成果类型: Article
• 署名作者: Davis, Erik; Sethuraman, Sunder
• 署名单位: University of Arizona
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/18-AAP1414
• 发表日期: 2019
• 页码: 1446-1486
• 关键词: shortest paths; graphs

摘要

Given a cost functional F on paths gamma in a domain D subset of R-d, in the form 1 F(gamma) = integral(1)(0) f (gamma(t), gamma(t)) dt , it is of interest to approximate its minimum cost and geodesic paths. Let X-1,...X-n be points drawn independently from D according to a distribution with a density. Form a random geometric graph on the points where X-i and X-j are connected when 0 < vertical bar X-i - X-j vertical bar < epsilon, and the length scale epsilon = epsilon(n) vanishes at a suitable rate. For a general class of functionals F, associated to Finsler and other distances on D, using a probabilistic form of Gamma convergence, we show that the minimum costs and geodesic paths, with respect to types of approximating discrete cost functionals, built from the random geometric graph, converge almost surely in various senses to those corresponding to the continuum cost F, as the number of sample points diverges. In particular, the geodesic path convergence shown appears to be among the first results of its kind.