0

Suppose I have some n points (in my case, 4 points) in 3 dimensions. I want to determine both the point a which minimizes the squared distance to each of these n points, as well as the largest difference that can exist between the distance from an arbitrary point b and any two of these n points (i.e. the two "farthest points").

How can this be most efficiently accomplished? I know that, in 2 dimensions and with 3 points, the solution to the point that minimized distance is the centroid of the triangle formed by the 3 points, and the solution to the largest difference can be found by taking a point located precisely at one (any?) of the 3 points. It seems that the same should be true in 3 dimensions, although I am unsure.

10GeV
  • 453
  • 2
  • 14
  • well centroid could be used in any dimensionality, however the most distant points are more complicated, I would do an [OBB](https://stackoverflow.com/a/62284464/2521214) and then use 2 most distant points which form (touch) the OBB it would be `O(m^2)` however `m << n` where `n` is number of points – Spektre Dec 21 '20 at 08:51
  • 1
    Do you mean to minimize the *sum of the distances* ? –  Dec 21 '20 at 09:40
  • 1
    In 2D, the point that minimizes the sum of the distances is *not* the centroid. –  Dec 21 '20 at 09:49
  • (centroid minimizes the sum of the squared distances) – David Eisenstat Dec 21 '20 at 21:17

2 Answers2

1

I want to determine both the point that minimizes distance from each of these n points

The centroid minimizes the sum of the squared distances to every point in the set. But will not minimize the max distance (the farther distance) to the points.

I suspect that you are interested in computing the center and radius of the minimal sphere containing every point in the set. This is a classic problem in CG that can be solved in linear time quite easily in an approximate way, or exactly if you program the algorithm propossed by Emmerich Welzl.

If the number of points is as small as 4, an approximate solution is search the pair of point with maximum distance (there is 12 possible pairs) and compute the midpoint as center and half-distance as radius . Then, ensure that the other two points are also inside the sphere, or make it grow if necessary.

See more information at https://en.wikipedia.org/wiki/Bounding_sphere https://en.wikipedia.org/wiki/Smallest-circle_problem

Rockcat
  • 3,002
  • 2
  • 14
  • 28
0

The largest difference between the distances of a point to two given points is achieved when the three points are aligned and the unknown point is "outside" (there are infinitely many solutions). In this configuration, the difference is just the distance between the two given points.

If you mean to maximize all differences simultaneously (or rather the sum of differences), you must go to infinity in some direction. That direction maximizes the sum of the lengths of the projections of all edges.