2

I am meeting with a problem, say I have already know the coordinates of N points (a1,a2,a3....) in 3D space. And I have a new point, say x. I only know the distances from x to the known N points. Is there an efficient method to find the coordinate of x?

If all of the distance are error-free, I think I can random pick up 3 known points, and compute the coordinate of x. But the distance are not error-free, i.e. if I use different points as reference, the coordinate of x maybe differ a lot.

So I want to use all of those N distance to compute the coordinate of x. Can anyone give some solution or suggestions?

cityCoder
  • 43
  • 2
    Typically, $3$ points will not be enough to fix the point anyway. Usually, when there exists one point with the specified distances, there will exist two such points. – Robert Bryant Mar 03 '15 at 13:50
  • 4
    This looks like a GPS problem, so just try to find out what algorithms they are using. –  Mar 03 '15 at 14:00
  • One suggested algorithm for $N=4$ (minimize sum of squared errors) is describe in the earlier analogous question here. – Joseph O'Rourke Mar 04 '15 at 01:48

1 Answers1

1

See this wiki page. (Location estimation in sensor networks), or read the gazillion papers on the subject :)

Igor Rivin
  • 25,994
  • 1
  • 19
  • 40