Learning random points from geometric graphs or orderings

Josep Diaz, Colin McDiarmid, Dieter Mitsche

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$.…