<p>(I don't have a real answer, but this was too long for a comment, so posting it here anyway...)</p>

<p>I <em>suspect</em> that the problem is NP-hard, by reduction from the subset sum problem. A proof idea:</p>

<p>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}$.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-19T22:29:46.773Z
interesting idea - thanks. a quick clarification question - what allows you to assume all 1-neighbor edges are vertical?
Lev Reyzin
CC BY-SA 2.5
2010-08-19T22:40:04.500Z
I'm only assuming that the edges 1-2, 3-4, ... are vertical. Of course you can choose the orientation of the edge 1-2 arbitrarily, and define that it is "vertical". Then there are only two possible configurations for the edge 3-4: either it is vertical *or* you have "flipped" (mirrored) along the edge 2-3. We'd like to avoid the second possibility which complicates the proof; see the part "so far so good..." for a possible idea of how to handle that.
Jukka Suomela
CC BY-SA 2.5
2010-08-20T15:02:42.787Z
I see - nice idea
Lev Reyzin
CC BY-SA 2.5
2010-08-29T14:36:59.590Z
Thm 4.1 (pg 50) of http://www.cs.yale.edu/homes/dkg6/papers/thesis.pdf this thesis says that the square of any 2-connected graph has a unique localization.  Given you presented a global localization that is found by solving subset sum, we know there are no more answers (and do not have to worry about diagonal flips).  I think this finishes the proof!
Lev Reyzin
CC BY-SA 2.5
2010-08-19T21:57:53.147Z
2010-08-19T21:57:53.147Z
Jukka Suomela
<p>It is actually NP-hard. See the following paper for references.</p>

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

CC BY-SA 2.5
2010-08-20T09:31:25.133Z
Do the references actually cover the special case mentioned in OP? That is, your graph topology is the square of a cycle?
Jukka Suomela
CC BY-SA 2.5
2010-08-20T13:22:27.783Z
You are so right. It covers only embeddings in to R^d.
Imran Rauf
CC BY-SA 2.5
2010-08-20T14:59:40.263Z
Good reference though - thanks
Lev Reyzin
CC BY-SA 2.5
2010-08-20T09:04:35.087Z
2010-08-20T09:04:35.087Z
Imran Rauf
<p>Drineas et al. wrote the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.3194&amp;rep=rep1&amp;type=pdf" rel="nofollow"><em>Distance Matrix Reconstruction from Incomplete Distance Information for Sensor Network Localization</em></a>. But what they achieve is probably not exactly what you ask for : they compute the whole distance map from an incomplete one, even in the presence of noise and node failures.</p>

CC BY-SA 2.5
2010-08-19T18:55:22.037Z
2010-08-19T18:55:22.037Z
Sylvain Peyronnet
<p>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.</p>

<p>The problem is: </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>I don't know of a polynomial time algorithm.</p>

<p>This is motivated by problems in <a href="http://www.cs.yale.edu/homes/dkg6/papers/thesis.pdf" rel="nofollow noreferrer">localization in sensor networks</a>, where agents, placed ad-hoc, can wirelessly communicate with their lexicographic neighbors, and we want to reconstruct their positions.</p>

<p>I don't know much about geometry / localization problems, so this might be easy or known.  The closest problem I know about is the <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/101#101">Turnpike problem</a>, recently pointed out on this forum by @Suresh Venkat.</p>

CC BY-SA 2.5
2010-08-19T16:41:58.703Z
well-defined?
if two points are permitted to land on the same point in R^2, then you can make hinges.
RJK
CC BY-SA 2.5
2010-08-19T16:52:21.983Z
sorry fixing...
Lev Reyzin
CC BY-SA 2.5
2010-08-19T18:51:16.490Z
Lev, it seems like tex is now enabled. can you try to edit your post to use latex and see if it works ?
Suresh Venkat
CC BY-SA 2.5
2010-08-19T19:08:31.463Z
you haven't clarified whether given a distance d I know which pair (i,j) made it. the difference is crucial
Suresh Venkat
CC BY-SA 2.5
2010-08-19T20:53:18.547Z
@suresh - I have clarified your question - we do know the corresponding distances.  also tex support is great! @Jukka - thanks I will check out your link.
Lev Reyzin
<cg.comp-geom>
Complexity of Localization in Wireless Networks
Lev Reyzin
# Complexity of Localization in Wireless Networks

(Asked by: username_0 on 2010-08-19)

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](http://www.cs.yale.edu/homes/dkg6/papers/thesis.pdf), 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](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/101#101), recently pointed out on this forum by @username_2.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: well-defined? if two points are permitted to land on the same point in R^2, then you can make hinges.  
> **username_0**: sorry fixing...  
> **username_2**: Lev, it seems like tex is now enabled. can you try to edit your post to use latex and see if it works ?  
> **username_2**: you haven't clarified whether given a distance d I know which pair (i,j) made it. the difference is crucial  
> **username_0**: @suresh - I have clarified your question - we do know the corresponding distances.  also tex support is great! @Jukka - thanks I will check out your link.  

---

## 3 answers

### Answer by username_3 on 2010-08-19. Score: 4 | Accepted answer

(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.

> **Comments:**
> **username_0**: interesting idea - thanks. a quick clarification question - what allows you to assume all 1-neighbor edges are vertical?  
> **username_3**: I'm only assuming that the edges 1-2, 3-4, ... are vertical. Of course you can choose the orientation of the edge 1-2 arbitrarily, and define that it is "vertical". Then there are only two possible configurations for the edge 3-4: either it is vertical *or* you have "flipped" (mirrored) along the edge 2-3. We'd like to avoid the second possibility which complicates the proof; see the part "so far so good..." for a possible idea of how to handle that.  
> **username_0**: I see - nice idea  
> **username_0**: Thm 4.1 (pg 50) of http://www.cs.yale.edu/homes/dkg6/papers/thesis.pdf this thesis says that the square of any 2-connected graph has a unique localization.  Given you presented a global localization that is found by solving subset sum, we know there are no more answers (and do not have to worry about diagonal flips).  I think this finishes the proof!  

---

### Answer by username_4 on 2010-08-20. Score: 6

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

> **Comments:**
> **username_3**: Do the references actually cover the special case mentioned in OP? That is, your graph topology is the square of a cycle?  
> **username_4**: You are so right. It covers only embeddings in to R^d.  
> **username_0**: Good reference though - thanks  

---

### Answer by username_5 on 2010-08-19. Score: 4

Drineas et al. wrote the paper [*Distance Matrix Reconstruction from Incomplete Distance Information for Sensor Network Localization*](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.3194&rep=rep1&type=pdf). But what they achieve is probably not exactly what you ask for : they compute the whole distance map from an incomplete one, even in the presence of noise and node failures.


---

