{
  "id": "1711.06952",
  "version": "v1",
  "published": "2017-11-19T01:54:54.000Z",
  "updated": "2017-11-19T01:54:54.000Z",
  "title": "Approximating geodesics via random points",
  "authors": [
    "Erik Davis",
    "Sunder Sethuraman"
  ],
  "comment": "34 pages, 3 figures",
  "categories": [
    "math.PR",
    "math.OC",
    "math.ST",
    "stat.TH"
  ],
  "abstract": "Given a `cost' functional $F$ on paths $\\gamma$ in a domain $D\\subset\\mathbb{R}^d$, in the form $F(\\gamma) = \\int_0^1 f(\\gamma(t),\\dot\\gamma(t))dt$, it is of interest to approximate its minimum cost and geodesic paths. Let $X_1,\\ldots, 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<|X_i - X_j|<\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-19T01:54:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60D05",
      "58E10",
      "62-07",
      "49J55",
      "49J45",
      "53C22",
      "05C82"
    ],
    "keywords": [
      "random points",
      "approximating geodesics",
      "random geometric graph",
      "minimum cost",
      "sample points diverges"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}