Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.