# Finding the coordinates of an unknown point.

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.

-
Draw circles or annuli, and look for intersection points/areas. If you want algorithms, I'm sure they exist but I don't know them. For the optimal point in the imprecise case, the center of weight of the optimal area is a candidate. –  Lord_Farin Oct 12 '12 at 17:36

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.

-
Thanks for the help. The only thing I do not understand is the last part with OLS regression. Won't this produce a line of best fit not an optimal point? How should I go about getting the best point from the line? –  user1728853 Oct 17 '12 at 21:13
@user1728853: least squares produces the best estimate of the parameters. In your case, the parameters are the coordinates of $p$ Given $x,y$ coordinates of $p$, you calculate the distance to each of the $9$ other points, subtract the desired distance to $p$, square the errors and sum. Then perturb $p$ until the sum of squares is minimized. This gives $x$ and $y$, not a line. –  Ross Millikan Oct 17 '12 at 21:21
Thanks again for the explaining. Can you point to any examples of parameter estimation with least squares. All I am familiar with is using least squares to get a line of best fit. I don't follow exactly what you are explaining and I could't find any example by searching. Thanks again. –  user1728853 Oct 17 '12 at 22:49

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.

-
In my opinion the easiest way if you can pick beforehand your own set of "known points" is to use L=(-1,0), R=(1,0), D=(0,-1) and U=(0,1). I chose these names for left, right, down, and up. Then let $l,r,d,u$ be the distances from p to $L,R,D,U$ respectively; if $p=(x,y)$ you have the simple formulas $x=(r^2-l^2)/4$ and $y=(u^2-d^2)/4$. –  coffeemath Oct 12 '12 at 18:30