Learning random points from geometric graphs or orderings. Issue 2 (22nd April 2020)

• Record Type: Journal Article
• Authors: Díaz, Josep; McDiarmid, Colin; Mitsche, Dieter
• Is Part Of: Random structures & algorithms. Volume 57:Issue 2(2020)
• Page Start: 339
• Page End: 370
• Publication Date: 2020-04-22
• Subjects: approximate embedding -- random geometric graphs -- unit disk graphs -- vertex orders; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20922
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ) .