Finding the coordinates of an unknown point.

Question

I have 10 points on a 2D plane where I know the $(x,y)$ coordinates of 9 of the points. For 1 point, $p$, I do not know its location. Additionally, I have the distances from each of the known 9 points to $p$. How can I find the position of the unknown point, $p$?

Bonus: The distances to p from each of the 9 points is imprecise. How can I find the optimal point location given that there may be imprecision is the distances to p.

Thanks in advance for the help.

Answer 1

If you know the distance exactly, swinging a circle from any two of the points will give you two choices of $p$, which can be resolved using a third point. If $p$ is at $(x,y)$, one other point is $(a,b)$ at radius $r$ you have $(x-a)^2+(y-b)^2=r^2$ and the similar equation from the second point.

If the distances are imprecise, you can do the same exercise to find a starting point, then use a two-dimensional least squares fit, where the parameters are the coordinates of $p$. Instructions are in any numerical analysis book.

Answer 2

Suppose the points are $p_i = (x_i,y_i)$ for $i\in [1,10]$, and we need to find $p_1$. To start with, suppose that all distances are exact. Pick 3 points whose coordinates are known, say $p_2,p_3,p_4$. Then we have three equations:

$$ (x_1-x_i)^2 + (y_1-y_i)^2 = |p_1p_i|, i \in \{2,3,4\} $$

These represent 3 circles whose intersection point solves for $p_1$; the solution of these simultaneous equations gives $p_1$. Assuming exactness of distances, the point $p_1$ should be identical regardless of the other 3 points you choose.

If the distances are inaccurate, you need to do an optimal fit. Your objective is to find $(x_1,y_1)$ such that

$$ F = \sum _{i\in [2,10]} (x_i -x_1)^2 + (y_i-y_1)^2 - |p_1p_i|^2 $$

is minimized. You could solve this with a nonlinear solver, e.g. fmincon in Matlab.

Answer 3

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.