找到到其他点集的距离之和最小的点
我有一组 (X) 点（不是很大，比如说 1-20 个点）和第二组 (Y)，更大的一组点。我需要从 Y 中选择某个点，该点到 X 的所有点的距离之和最小。
我想到了一个想法，将X视为多边形的顶点并找到该多边形的质心，然后从Y中选择距离质心最近的点。但我不确定质心是否最小化其到多边形顶点的距离总和，所以我不确定这是否是一个好方法？有什么算法可以解决这个问题吗？
点由地理坐标定义。
I have one set (X) of points (not very big let's say 1-20 points) and the second (Y), much larger set of points. I need to choose some point from Y which sum of distances to all points from X is minimal.
I came up with an idea that I would treat X as a vertices of a polygon and find centroid of this polygon, and then I will choose a point from Y nearest to the centroid. But I'm not sure whether centroid minimizes sum of its distances to the vertices of polygon, so I'm not sure whether this is a good way? Is there any algorithm for solving this problem?
Points are defined by geographical coordinates.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
多边形的质心可能不正确，但这样的点是存在的。
在论文：n-椭圆和最小距离问题中，表明如果点（称为焦点，您的 X 组) 不共线，则
存在一个唯一点（称为中心），其距离总和最小化。该点使得从该点到焦点的单位向量之和为零！
距离和为常数的点的轨迹是包含中心的凸曲线（称为 n 椭圆）
距离 D 的 n 椭圆完全包含任何其他距离 D' 的 n 椭圆，其中 D' < 。
因此，您可以执行某种类型的爬山算法来找到中心。
当然，这些 n 个椭圆不一定是圆形，因此仅选择最接近中心的点可能行不通，但可能是一个很好的近似值。
您也许可以对 20 个点（如果这些点是固定的）进行一些预处理，以找出一个好的分区方案（基于上述信息）。
希望有帮助。
Centroid of the polygon might not be right, but such a point exists.
In the paper: n-ellipses and the minimum distance problem, it is shown that if the points (called foci, your set of X) are not collinear then
There is a unique point (called center) for which the sum of distances are minimized. This point is such that the sum of unit vectors from that point to the foci is zero!
The locus of points for which the sum of distances is constant is a convex curve (called an n-ellipse) containing the center
The n-ellipse for distance D completely contains the n-ellipse for any other distance D' for which D' < D.
Thus you can do some type of hill climbing algorithm to find the center.
Of course these n-ellipses are not necessarily circles, so just picking the point closest to the center might not work, but might be a good approximation.
You can perhaps do some preprocessing on the 20 points (if those are fixed) to figure out a good partitioning scheme (based on the above information).
Hope that helps.
如果要最小化距离的平方和（而不是距离的总和），则最小化该和的点是 X 中点的平均值。
证明：
当导数为零时，总和最小化，当
Nx = x0+x1+...时发生，因此x = (x0+x1+...)/N导数围绕该点对称，并且该函数是二次的，所以我很确定 Y 中最接近该平均点的点是最好的。
最小化距离比较困难，但我怀疑相同的算法，在您测试的 Y 集中有更多的余地，也会起作用。
If you want to minimize the sum of the squares of the distances (not the sum of the distances), then the point that minimizes that sum is the average of the points in X.
Proof:
the sum is minimized when the derivative is zero, which occurs when
Nx = x0+x1+..., sox = (x0+x1+...)/NThe derivative is symmetric around this point, and the function is quadratic, so I'm pretty sure the closest point in Y to this average point is the best.
Minimizing the distances is harder, but I suspect the same algorithm, with more leeway in the set of Ys that you test, would work also.
因为您想要最小的距离总和，所以我相信您可以将点集 X 减少到其空间平均值。然后，您可以使用 KDTree 或某种空间分区树来查找 Y 中最接近 X 的空间均值的点。与检查所有可能的点相比，使用空间分区树可以节省大量工作。
Because you want the minimal sum of distances I believe that you can reduce the set of points X to its spatial mean. Then you can use a KDTree or some sort of spatial partitioning tree to find the point in Y closest to the spatial mean of X. Using a spatial partitioning tree can save a good bit of work compared to checking all the possible points.
请原谅我建议使用暴力。
根据问题的提出方式，我们不知道 X,Y 位于何处。
假设X为30分，Y为1000分。
然后对于 Y 的每个点求和 30 个距离。
总共30000次计算，一下子就完成了。
这保证了最低限度。
找到 X 的某个“中心”并选择最接近的 Y 仅是一个近似解。
更有趣的问题是单独为X找到这样一个点。忽略Y。
仅对于 X 三点，费马-托里切利点解决了问题。
Excuse me for suggesting brute force.
The way the question is posed we do not know where X,Y lie.
Suppose X is 30 points, Y is 1000 points.
Then for each point of Y sum 30 distances.
Altogether 30000 calculations, done in a jiffy.
This guarantees a minimum.
Finding some "center" of X and choosing the closest Y will be an approximate solution only.
The more interesting question is to find such a point for X alone. ignore Y.
For X three points only, the Fermat-Torichelli point solves the problem.