Let distinct points $1 ... n$ sit in $\mathbb{R}^2$.  We say points $i$ and $j$ are neighbors if $|i-j| < 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.
Complexity of Localization in Wireless Networks
cg.comp geom
(I don't have a real answer, but this was too long for a comment, so posting it here anyway...)I suspect that the problem is NP-hard, by reduction from the subset sum problem. A proof idea:Reduction: if the $i$th element in the subset sum instance is $x_i$, then the distance between nodes $2i-1$ and $2i$ is $s$, distance between $2i-1$ and $2i+1$ is $x_i$, distance between $2i$ and $2i+2$ is also $x_i$, and distance between $2i$ and $2i+1$ is $\sqrt{s^2 + x_i^2}$.Assume that the edges between $2i-1$ and $2i$ for all $i$ are vertical. Then the whole graph consists of a chain of rectangles with diagonals. However, you can flip each rectangle so that $2i+2$ is either on the left side of $2i$ or the right side of $2i$. And you need to find the right subset of flips so that the distance between the last node $n = 2k$ and the node $2$ is correct (and the distance between $2k-1$ and $1$ is correct and the distance between $2k-1$ and $2$ is correct).So far so good, but our rectangles aren't really rigid; we could also flip along the diagonal. However, I think if we choose a nasty value $s$, then perhaps we could show that everything goes horribly wrong if we ever flip along a diagonal (e.g., the coordinates of $2k$ won't be rational)? This may require some tweaks in the values $x_i$, though.