12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ well-defined? if two points are permitted to land on the same point in R^2, then you can make hinges. $\endgroup$ – RJK Aug 19 '10 at 16:41
  • $\begingroup$ sorry fixing... $\endgroup$ – Lev Reyzin Aug 19 '10 at 16:52
  • 1
    $\begingroup$ Lev, it seems like tex is now enabled. can you try to edit your post to use latex and see if it works ? $\endgroup$ – Suresh Venkat Aug 19 '10 at 18:51
  • $\begingroup$ you haven't clarified whether given a distance d I know which pair (i,j) made it. the difference is crucial $\endgroup$ – Suresh Venkat Aug 19 '10 at 19:08
  • $\begingroup$ @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. $\endgroup$ – Lev Reyzin Aug 19 '10 at 20:53
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ interesting idea - thanks. a quick clarification question - what allows you to assume all 1-neighbor edges are vertical? $\endgroup$ – Lev Reyzin Aug 19 '10 at 22:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Aug 19 '10 at 22:40
  • $\begingroup$ I see - nice idea $\endgroup$ – Lev Reyzin Aug 20 '10 at 15:02
  • $\begingroup$ Thm 4.1 (pg 50) of 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! $\endgroup$ – Lev Reyzin Aug 29 '10 at 14:36
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Do the references actually cover the special case mentioned in OP? That is, your graph topology is the square of a cycle? $\endgroup$ – Jukka Suomela Aug 20 '10 at 9:31
  • 1
    $\begingroup$ You are so right. It covers only embeddings in to R^d. $\endgroup$ – Imran Rauf Aug 20 '10 at 13:22
  • $\begingroup$ Good reference though - thanks $\endgroup$ – Lev Reyzin Aug 20 '10 at 14:59
4
$\begingroup$

Drineas et al. wrote the paper Distance Matrix Reconstruction from Incomplete Distance Information for Sensor Network Localization. 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.