Suppose that there is a family of n random points Xv for v¿V, independently and uniformly distributed in the square [-n--v/2,n--v/2]2. We do not see these points, but learn about them in one of the following two ways.
Suppose first that we are given the corresponding random geometric graph G, where distinct vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Assume that the threshold distance r satisfies n3/14«r«n1/2. We shall see that the following holds with hi...
Suppose that there is a family of n random points Xv for v¿V, independently and uniformly distributed in the square [-n--v/2,n--v/2]2. We do not see these points, but learn about them in one of the following two ways.
Suppose first that we are given the corresponding random geometric graph G, where distinct vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Assume that the threshold distance r satisfies n3/14«r«n1/2. We shall see that the following holds with high probability. Given the graph G (without any geometric information), in polynomial time we can 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 being given the graph 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 the much smaller displacement error O(logn----v).