Complexity of Localization in Wireless Networks Let distinct points $1 ... n$ sit in $\mathbb{R}^2$.  We say points $i$ and $j$ are neighbors if $|i-j| &lt; 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, wrapping around.

The problem is: 


  For each pair of neighbors we are given their pairwise distances (and we know which distance corresponds to which points), and we want to reconstruct the
  pairwise distances of all points.  My
  questions is, what is the complexity
  of this localization problem?


I don't know of a polynomial time algorithm.

This is motivated by problems in localization in sensor networks, where agents, placed ad-hoc, can wirelessly communicate with their lexicographic neighbors, and we want to reconstruct their positions.

I don't know much about geometry / localization problems, so this might be easy or known.  The closest problem I know about is the Turnpike problem, recently pointed out on this forum by @Suresh Venkat.
It is actually NP-hard. See the following paper for references.

Sriram V. Pemmaraju, Imran A. Pirwani: Good Quality Virtual Realization of Unit Ball Graphs. ESA 2007: 311-322