Learning random points from geometric graphs or orderings. Issue 2 (22nd April 2020) - Díaz, Josep; McDiarmid, Colin; Mitsche, Dieter
Abstract : Let X v for v ∈ V be a family of n iid uniform points in the square 𝒮 n = − n / 2, n / 2 2 . Suppose first that we are given the random geometric graph G ∈ G ( n, r ), where vertices u and v are adjacent when the Euclidean distance d E (X u, X v ) is at most r . Let n 3/14 ≪ r ≪ n 1/2 . Given G (without geometric information), in polynomial time we can with high probability approximately reconstruct the hidden embedding, in the sense that "up to symmetries, " for each vertex v we find a point within distance about r of X v ; that is, we find an embedding with "displacement" at most about r . Now suppose that, instead of G we are given, for each vertex v, the ordering of the other vertices by increasing Euclidean distance from v . Then, with high probability, in polynomial time we can find an embedding with displacement O ( log n ) .