Determine coordinates from distance vector

Question

The problem I stand in front of is that I need to determine the coordinates of some nodes. The information I have in hand is the distance from all nodes to all nodes. That is every node has a vector with its distance to all other nodes and from that I want to determine the coordinate for all nodes. What needs to be had in mind is that the distances are measured and thus will have some error.

The question is what is the best way to solve this problem.

My thoughts so far is to choose one point as $(0,0,0)$ and another points as $(d_{10},0,0)$, where $d_{10}$ is the distance between node $0$ and node $1$.

Then describe the relations between the distanced and coordinates for all nodes to all nodes. Here the equation from node $0$ to node $1$

$$f(\bar{x})_{1,0} = \sqrt{(x_1-x_0)^2+(y_1-y_0)^2+(z_1-z_0)^2} - d_{10} =0$$

I will then do that for all nodes and run them through a non-linear optimization, where the objective is to

$$\text{min}~ \sum{f(\bar{x})_{i, i-1}}$$

Is this a good way to go or are there any other solutions that would be better?

An interesting add on is how does the problem change when not all nodes has the distance from each other.

Answer 1

If I properly understand, you have $n$ points of unknown cooredinates $(x_i,y_i,z_i)$ and you know all the distances $$d_{ij}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}$$ This makes $\frac{n(n-1)}2$ equations for $3(n-1)$ variables since, as you decided (good idea, for sure) to fix one of the points at the origin. So, in principle, as soon as $n \geq 6$, there could be a solution.

For sure, as you wrote, the most natural function to minimize would be $$\Phi=\sum_{i=1}^{n-1} \sum_{j=i+1}^n\left(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}-d_{ij} \right)^2$$

Personally, I think that I should first try to minimize (at least in a first step) $$\Psi=\sum_{i=1}^{n-1} \sum_{j=i+1}^n\left({(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}-d^2_{ij} \right)^2$$ which is more than likely better conditioned than $\Phi$.

In principle, this could work if some distances are missing as long as the total number of distances is $\geq 3(n-1)$.

Answer 2

Considering the objective function as

$$ \sum_i\sum_j \left((x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2-d^2_{ij}\right)^2 $$

the script below (in MATHEMATICA) shows the initial set of random points in red and the solution obtained after the minimization in blue. There are two anchored points. The first and the last. Those points are given as restrictions.

n = 5;
pts = RandomReal[{-10, 10}, {n, 3}];
DD = Table[(pts[[i]] - pts[[j]]).(pts[[i]] - pts[[j]]), {i, 1, n}, {j, 1, n}];
For[i = 1; s = 0, i <= n, i++,
  For[j = i, j <= n, j++, If[i != j, s += ((Subscript[x, i] - Subscript[x, j])^2 + (Subscript[y, i] - Subscript[y, j])^2 + (Subscript[z, i] - Subscript[z, j])^2 -DD[[i, j]])^2]
  ]
]
vars = Variables[s];
pts1 = pts[[1]];
ptsn = pts[[n]];
const1 = Thread[{Subscript[x, 1], Subscript[y, 1],Subscript[z, 1]} == pts1];
const2 = Thread[{Subscript[x, n], Subscript[y, n],Subscript[z, n]} == ptsn];
constrs = Join[const1, const2];
sol = Minimize[Join[{s}, constrs], vars];
Print["Minimization error = ", sol[[1]]]
ptsol = Table[{Subscript[x, k], Subscript[y, k], Subscript[z, k]} /.sol[[2]], {k, 1, n}]
t1 = Table[Graphics3D[{Red, PointSize[0.02], Point[pts[[k]]]}], {k, 1, n}];
e1 = Table[Graphics3D[{Red, Line[{pts[[i]], pts[[j]]}]}], {i, 1, n}, {j, 1,  n}];
t2 = Table[Graphics3D[{Blue, PointSize[0.02], Point[ptsol[[k]]]}], {k, 1, n}];
e2 = Table[Graphics3D[{Blue, Line[{ptsol[[i]], ptsol[[j]]}]}], {i, 1, n}, {j, 1, n}];
Show[e1, e2, t1, t2]

Follows a series of examples.

n = 3

n = 4

n = 5

n = 15

NOTE

This problem has many symmetries so unexpected solutions are allowed. More anchor points can be considered in order to reduce the possible solutions.