Name
Abstract | ||
|---|---|---|
Let X-v for v is an element of V be a family of n iid uniform points in the square <SIC>& 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). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/rsa.20922 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
approximate embedding,random geometric graphs,unit disk graphs,vertex orders | Binary logarithm,Graph,Combinatorics,Embedding,Vertex (geometry),Euclidean distance,Time complexity,Random geometric graph,Mathematics,Homogeneous space | Journal |
Volume | Issue | ISSN |
57.0 | 2.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| Colin McDiarmid | 2 | 1071 | 167.05 |
| Dieter Mitsche | 3 | 141 | 26.08 |