Recovering Global Point Position from Incomplete Information for a Poisson Point Process in a 2-D Box

Abstract

We will discuss the problem of point recovery for a Poisson Point Process for which the only information available is the distance between pairs of points that are relatively close together. Little is known about this for a two dimensional PPP. We make some progress on this problem when the information is noise-free, and the PPP takes values in a square of size √n and find the smallest threshold ρ (dependent on n) such that, if given the distances between pairs of points at a distance less than ρ, recovery is possible with high probability. Moreover, we show that recovery is impossible with high probability otherwise.

In the second part of this paper, we tackle the noisy case in which information about the distance between a pair of points is available with an exponentially decreasing probability in the distance between the points and show that recovery is impossible with high probability when the distance between two points x, y is known with probability px,y = qe−|x−y| for some constant q < 1. We also show that there exists a constant α^∗ such that recovery becomes possible with high probability when px,y = e^(−α|x−y|/√log n) for any α ≤ α^∗.