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$
5
  • $\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, 2010 at 16:41
  • $\begingroup$ sorry fixing... $\endgroup$
    – Lev Reyzin
    Aug 19, 2010 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$ Aug 19, 2010 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$ Aug 19, 2010 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, 2010 at 20:53

3 Answers 3

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.

$\endgroup$
4
  • $\begingroup$ interesting idea - thanks. a quick clarification question - what allows you to assume all 1-neighbor edges are vertical? $\endgroup$
    – Lev Reyzin
    Aug 19, 2010 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$ Aug 19, 2010 at 22:40
  • $\begingroup$ I see - nice idea $\endgroup$
    – Lev Reyzin
    Aug 20, 2010 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, 2010 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

$\endgroup$
3
  • 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$ Aug 20, 2010 at 9:31
  • 1
    $\begingroup$ You are so right. It covers only embeddings in to R^d. $\endgroup$
    – Imran Rauf
    Aug 20, 2010 at 13:22
  • $\begingroup$ Good reference though - thanks $\endgroup$
    – Lev Reyzin
    Aug 20, 2010 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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