## Publication Date:

September 2020

## Journal:

RANDOM STRUCTURES & ALGORITHMS

## Last Updated:

2021-03-27T08:05:31.25+00:00

## Issue:

2

## Volume:

57

## DOI:

10.1002/rsa.20922

## 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})$.

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:

## Submitted to ORA:

Not Submitted

## Publication Type:

Journal Article