[Math] Finding the 3D coordinates of an unknown point from three known points

geometry

How can I find the coordinates $(x,y,z)$ in a $3d$ space when,

A) the unknown point is $(x,y,z)$;

B) there are three known points viz. $(a1,b1,c1)$, $(a2,b2,c2)$ and $(a3,b3,c3)$;

C) the distances from the three known points are $D1$, $D2$, $D3$, respectively.

Best Answer

It would involve solving a system of 3 equations with 3 unknowns, where the solution $(x,y,z)$ represents the intersection point of the following three 3D spheres: $$ (x-a_1)^2 + (y-b_1)^2 + (z-c_1)^2 = (D_1)^2\\ (x-a_2)^2 + (y-b_2)^2 + (z-c_2)^2 = (D_2)^2\\ (x-a_3)^2 + (y-b_3)^2 + (z-c_3)^2 = (D_3)^2 $$

The algorithm

Given a distance matrix $D_{ij}$, define $$M_{ij} = \frac {D^2_{1j}+D^2_{i1}-D^2_{ij}} 2 \,.$$ One thing that is good to know in case the dimensionality of the data that generated the distance matrix is not known is that the smallest (Euclidean) dimension in which the points can be embedded is given by the rank $k$ of the matrix $M$. No embedding is possible if $M$ is not positive semi-definite.

The coordinates of the points can now be obtained by eigenvalue decomposition: if we write $M = USU^T$, then the matrix $X = U \sqrt S$ (you can take the square root element by element) gives the positions of the points (each row corresponding to one point). Note that, if the data points can be embedded in $k$-dimensional space, only $k$ columns of $X$ will be non-zero (corresponding to $k$ non-zero eigenvalues of $M$).

Why does this work?

If $D$ comes from distances between points, then there are $\mathbf x_i \in \mathbb R^m$ such that $$D_{ij}^2 = (\mathbf x_i - \mathbf x_j)^2 = \mathbf x_i^2 + \mathbf x_j^2 - 2\mathbf x_i \cdot \mathbf x_j \,.$$ Then the matrix $M$ defined above takes on a particularly nice form: $$M_{ij} = (\mathbf x_i - \mathbf x_1) \cdot (\mathbf x_j - \mathbf x_1) \equiv \sum_{a=1}^m \tilde x_{ia} \tilde x_{ja}\,,$$ where the elements $\tilde x_{ia} = x_{ia} - x_{1a}$ can be assembled into an $n \times m$ matrix $\tilde X$. In matrix form, $$M = \tilde X \tilde X^T \,.$$ Such a matrix is called a Gram matrix. Since the original vectors were given in $m$ dimensions, the rank of $M$ is at most $m$ (assuming $m \le n$).

The points we get by the eigenvalue decomposition described above need not exactly match the points that were put into the calculation of the distance matrix. However, they can be obtained from them by a rotation and a translation. This can be proved for example by doing a singular value decomposition of $\tilde X$, and showing that if $\tilde X \tilde X^T = X X^T$ (where $X$ can be obtained from the eigenvalue decomposition, as above, $X = U\sqrt S$), then $X$ must be the same as $\tilde X$ up to an orthogonal transformation.

[Math] Finding the coordinates of an unknown point.

You can't find the location of p if it happens that your nine other points happen to lie on a single line. For in that case if u,v are mirror images of each other in the line (neither being on the line) and p happened to be at either u or v, we couldn't determine which it was, u or v. This is because any point on the line is equidistant from u and v, in turn because the line is the perpendicular bisector of the segment joining u to v.

If the nine points are not all on the same line, you can pick any three which are not all on a line, and only using the distances to those three you can get the location of p. So in this case you only need to actually use three of the known distances. I think if you look up how a GPS system works, you can get the related formulas. But anyway it's fairly easy geometry.

Lastly, if you are able to choose beforehand where the points are, there is probably an optimal way to place a certain number of them in order to (1) be able to figure out where p is from the distances and (2) have a reasonably simple formula from the distances to the coordinates of p. Requirements (1) and (2) together might mean one should place say 4 points rather than 3. Certainly I think there isn't a much better way using 9 instead of fewer known points, in satisfying both (1) and (2) the best way.

Best Answer

Related Solutions

Geometry – Finding the Coordinates of Points from Distance Matrix

The algorithm

Why does this work?

[Math] Finding the coordinates of an unknown point.

Related Question