[Solved]: Recovering a point embedding from a graph with edges weighted by point distance

Problem Detail: 

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 distance sin 3d, how expensive is it to determine if an embedding is possible at all?

Asked By : Craig Gidney

Answered By : Craig Gidney

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28642