Recovering a point embedding from a graph with edges weighted by point distance

Question

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the distance between the points.

Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.

In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p_0$ to be at $(0,0,0)$, then pick a neighboring point $p_1$ and place it at $(d_{0,1},0,0)$, then a common neighbor $p_2$ gets triangulated onto the XY plane, then a final common neighbor $p_3$ gets triangulated into the half-space $z > 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.

On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.

Which raises the questions:

• How expensive is it to find a solution?
• How do you determine if a solution is unique, up to translation/rotation/mirroring? Is 3-connectedness sufficient? Necessary?
• What sorts of conditions make the problem trivial?
• If I don't promise the edge weights actually correspond to point distances in 3d, how expensive is it to determine if an embedding is possible at all?

Answer 1

One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape.

Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d_{v,w}$, then the spring is chosen so it ideally wants to be of length $d_{v,w}$ (it can be longer or shorter, but this costs energy). We now want to solve for a set of positions that minimize the total energy. Suppose each vertex $v$ is placed at point $x_v \in \mathbb{R}^3$. Then the total energy of this arrangement will be

$$E(x) = \sum_{(v,w) \in E} (\text{distance}(x_v,x_w) - d_{v,w})^2.$$

Here the $d_{v,w}$'s are given (they are the weights on the edges), and we want to solve for the $x_v$'s (they are the coordinates of the points).

We can solve for an arrangement $x$ that minimizes this total energy. This arrangement then provides a reasonable candidate for the positions of the points. This is an optimization problem, and there are standard techniques for solving this kind of optimization problem. See, e.g., the article Network Solutions by Erica Klarreich.

I don't think there any guarantee this will provide the correct desired solution. It's possible that the optimization problem might settle to a different optimum that doesn't reflect the actual arrangement of points you were looking for. However, if your graph is sufficiently dense, I suspect it might often work and give you the desired solution.

---

Footnote: Of course even in the best case we can only solve this problem up to translation, rotation, and reflection since those transformations preserve all distances. Thus, you can't expect a unique solution -- but you might hope that the solution is unique up to translation, rotation, and reflection.

---

Finally, there's a lot of work on embedding graphs into $\ell_2$ space, while minimizing the distortion of the embedding. That's very related; you are basically asking for a zero-distortion embedding into $\ell_2$. Thus, the techniques developed in that context might be useful for your problem, too. Typically, that work focuses on finding a low-distortion embedding, because that work focuses on the case where there is no perfect embedding that makes all the distances match exactly, so instead it looks for a low-distortion solution (one where most edge distances match pretty well) -- so that work is focused on a slightly different problem. However, it's possible that their techniques might be effective in your situation as well. It's worth a try.

Answer 2

The problem is NP-Complete. The positions of the points is a good certificate, so it's in NP, and you can encode circuits into the "is there a satisfying set of points?" problem.

Reduction from Circuit Evaluation to Distance Embedding

We're going to reduce circuit evaluation into a distance embedding problem by creating a coordinate system, putting logical bits in it, wiring bits to be equal, and creating widgets for NOT and AND gates.

1. Coordinates. We need some kind of coordinate system that we can position points with. Do this by creating a "base" tetrahedron of points. Add four points all declared to be a distance of $1$ from each other. This forces the shape of those four points into a tetrahedron. We can position other points relative to our tetrahedron coordinate system by specifying their distance to each of the four corners of the base. The tetrahedron can be translated and rotated and reflected, but the same thing will happen to all the other points as well.

2. Bits. To make a bit, we position a triangle of points relative to the base tetrahedron. The triangle's normal must point upward along the Z axis, so that the triangle is parallel to the XY plane (in tetrahedron coordinates). Also its edges must have length $1$. With that done, we add a "value" point $v$, specified to be a distance of $1$ from the other three. We don't connect $v$ to the base coordinate system. This gives it two possible positions: centered $\frac{1}{\sqrt{3}}$ above or below the triangle, as the final corner of a tetrahedron. The bit is ON if the point is above the triangle, and OFF if it's below.

3. Wires. We can force two bits to be equal by saying the distance between their value points is equal to the distance between the centers of their triangles. There is one exception: when the top or bottom corner of one of the bits exactly lines up with the center plane of the other. In that case we first use a wire to move one of the bits vertically.

4. NOT. We can get the negation of a bit by adding a second value point $w$ to the same triangle, but requiring that $w$ be a distance of $\frac{2}{\sqrt{3}}$ from $v$. This forces $w$ to take the position opposite of $v$, with respect to the triangle, giving us a bit with the opposite value.

5. IMPLIES. The equidistant issue we had to work around with the wires is actually quite useful. When the bits line up in that way, which we can force with a vertical wire, the higher one implies the lower one. If the higher one is true, only the top of the lower one is the right distance away. If the higher one is false, both the top and bottom are the right distance away.

6. AND. To make a bit $C$ be equal to $A$ AND $B$, we need two implications and a widget to force equality when $A$ and $B$ agree. The implications are just $C \implies A$ and $C \implies B$. To make the widget we move $A$ and $B$ vertically so they're on the same level and a distance $\frac{2}{\sqrt 3}$ apart, then we move $C$ to be equidistant between them. We then add a points $S_A$ and $S_B$ a distance $\frac{\sqrt 2 - 1}{2 \sqrt 3}$ from $A$ and $B$'s value points respectively, and force the distance between $S_A$ and $S_B$ to be $\frac{\sqrt 2 + 1}{\sqrt 3}$. We also add a point $S_C$ a distance $\frac{\sqrt 2 + 1}{2 \sqrt 3}$ from both $S_A$ and $S_B$. This creates a chain between $A$ and $B$'s value points, with $S_C$ at the chain's center. When $A \neq B$, the chain is stretched to the limit and $S_C$ is in the center of $C$'s triangle. When $A = B$ the chains links are forced to go in exact opposite directions, pushing it to the limit and placing $S_C$ on $C$'s value point equal to $A$. To force $C$'s value point, we insert a point $S_D$ a distance $\frac{1}{2 \sqrt 3}$ from both $S_C$ and $C$'s value point. This doesn't constrain $C$'s value point when $A \neq B$, but forces $A=B=C$ when $A=B$.

With those elements, you can encode any circuit into a distance embedding. The inputs become bits, gates get decomposed into NOTs and ANDs introducing new bits as necessary, and that's it. Force the position of the output to be true, and you get your satisfiability problem.

Answer 3

Partial answer on uniqueness: 3-connectedness is not sufficient.

Minimal counter example: cube graph ($Q_3$ of the Hypercube Graph family)

To see how fixing the length of all edges in $Q_3$ does not give positions to vertices in 3-d space that is unique up to translation/rotation/mirroring, look at how you can flatten a cardboard box (with 2 opposing faces removed).

Take the corners of cardboard box to be the vertices of interest. Each corner of a cardboard box have fixed distance from other corners which it shares a box's face with.

While the resulting graph has even more edges than $Q_3$, it still allows the cardboard box to be flatten down --- a transformation which can not be produced by translation/rotation/mirroring.

Answer 4

this is known as the following problem and occurs eg with reconstructing coordinates from sensor networks that can measure distance to nearby nodes, & this paper can serve as a mini-survey along with leading algorithm(s). a leading method is known as Singular Value Projection, another Singular Value Threshholding. the algorithms are generally based on matrix algebra & rank reduction. the paper implements both algorithms and gives some empirical analysis.

Euclidean Distance Reconstruction from Partial Distance Information Xu, Chen