1

I have an array of points with distances. I wish to find a point that best satisfies the condition that 

for (point_i, distance_i) in pointArray:
  abs(point - point_i) = distance_i

I think this could be solved with some kind of regression or least squares, but I'm having trouble with the problem formulation.

If anyone could help out, it would be greatly appreciated

Xzhsh
  • 2,239
  • 2
  • 22
  • 32

2 Answers2

4

You need to define "best" to have an answerable question.

What you probably want to do is define some sort of error function for how much being off from a given point matters, and then try to minimize the sum of the errors. The error function to use depends on what your actual problem is. For instance perhaps you want to use (length(point - point_i) - distance)2. That would be least squares. But perhaps you don't care so much about the absolute amount the distances are off, just the ratio between how far they are and how far you expected them to be. So you might use (length(point - point_i)/distance - 1)2. Perhaps you get the points and distances from a bunch of sensors. In that case the appropriate error function to use reflects how much uncertainty there is in your measurement of the distance.

Once you have an appropriate error function chosen, you then need to find a way to optimize it. The simplest way to do that is to calculate a gradient for your error function, and use that to follow a path finding algorithm to the lowest point. If your error function is well behaved, this should work, though not that fast. If you're ambitious you can use the multivariate Newton-Raphson method to find that point. This makes more assumptions about your error function, and will be a lot of work, but will converge much faster.

btilly
  • 43,296
  • 3
  • 59
  • 88
  • 1
    Thanks for the answer btilly. What I wanted to do here is actually reconstruct the sensor location from a bunch of range data. I have a somewhat noisy set of 3D points, and a set of distances from the camera, and I want to find where the camera should be – Xzhsh Feb 02 '11 at 21:21
  • @Xzhsh: Then your error function should reflect how uncertain you are about the range measurements. If it is a camera, then I'd guess that (length(point - point_i)/distance - 1)^2 is likely to be reasonable. – btilly Feb 02 '11 at 22:43
1

This problem is usually approached by with linear algebra, by solving for "least squares", which minimizes the square of the error.

This is how gps receivers find the "best fit" to give your coordinates. They take the set of "noisy" distances to all of the different satellites, and find a new set of distances that meet a single point which has the least, squared, error from the "noisy" distances.

There are many linear algebra libraries out there (the most predominant being linpack) which should have functions for solving these types problems.

brandon
  • 43
  • 5