Learning random points from geometric graphs or orderings
Josep Dı́az, Colin McDiarmid, Dieter Mitsche · Random Structures and Algorithms · 2020
Let Xv for v∈V be a family of n iid uniform points in the square . Suppose first that we are given the random geometric graph , where vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Let n3/14≪r≪n1/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 Xv; 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 .