Learning random points from geometric graphs or orderings
Learning random points from geometric graphs or orderings
复制标题
从几何图形或排序中学习随机点
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
D. Mitsche
中科院分区：
文献类型：
--
作者：
J. Díaz;C. McDiarmid;D. Mitsche
设Xv（v∈V）是正方形中n个一致点的一族？n=−n/2，n/22。设G∈G（n，r）是一个随机几何图，当欧氏距离dE（Xu，Xv）不超过r时，G的顶点u和v相邻.设n3/14 ≠ r1/2。给定G（没有几何信息），我们可以在多项式时间内以很高的概率近似地重建隐藏的嵌入，在这个意义上，“直到对称”，对于每个顶点v，我们找到一个距离Xv的r以内的点;也就是说，我们找到一个“位移”至多为r的嵌入。现在假设，而不是G，我们给出，对于每个顶点v，通过增加与v的欧几里得距离来排序其他顶点。然后，以很高的概率，在多项式时间内，我们可以找到位移为O（logn）的嵌入。
Let Xv for v∈V be a family of n iid uniform points in the square ?n=−n/2,n/22 . 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 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 O(logn) .
影响因子：
1.1
作者：
Arias-Castro, Ery;Channarond, Antoine;Pelletier, Bruno;Verzelen, Nicolas
通讯作者：
Verzelen, Nicolas