Author
Diaz, J
McDiarmid, C
Mitsche, D
Journal title
RANDOM STRUCTURES & ALGORITHMS
DOI
10.1002/rsa.20922
Issue
2
Volume
57
Last updated
2021-11-12T05:17:19.033+00:00
Page
339-370
Abstract
Suppose that there is a family of $n$ random points $X_v$ for $v \in V$,
independently and uniformly distributed in the square
$\left[-\sqrt{n}/2,\sqrt{n}/2\right]^2$ of area $n$. 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
$d_E(X_u,X_v)$ is at most $r$. If the threshold distance $r$ satisfies
$n^{3/14} \ll r \ll n^{1/2}$, then 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
$X_v$; 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(\sqrt{\log n})$.
Symplectic ID
923595
Download URL
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000527372200001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=4fd6f7d59a501f9b8bac2be37914c43e
Publication type
Journal Article
Publication date
September 2020
Please contact us with feedback and comments about this page. Created on 11 Oct 2018 - 17:30.