Learning random points from geometric graphs or orderings

摘要

Let X-v for v is an element of V be a family of n iid uniform points in the square & xdcae;n=-n/2,n/22. Suppose first that we are given the random geometric graph G is an element of 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)MUCH LESS-THANrMUCH LESS-THANn(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(logn).