我有一组 (X) 点(不是很大，比如 1-20 个点)和第二组 (Y)，更大的一组点。我需要从 Y 中选择一些点，从 X 到 all 点的距离总和最小。
我想出了一个想法，将 X 视为多边形的顶点并找到该多边形的质心，然后我将从 Y 中选择一个最接近质心的点。但是我不确定质心是否最小化了它到多边形顶点的距离之和，所以我不确定这是否是一个好方法？有解决这个问题的算法吗？
点由地理坐标定义。
最佳答案
多边形的质心可能不对，但这样的点是存在的。
论文中:n-ellipses and the minimum distance problem ，表明如果点(称为焦点，你的 X 集)不共线，则
有一个唯一点(称为中心)，距离总和最小。这一点使得从该点到焦点的单位向量之和为零!
距离和为常数的点的轨迹是包含中心的凸曲线(称为 n 椭圆)
距离 D 的 n 椭圆完全包含任何其他距离 D' 的 n 椭圆，其中 D' < D。
因此，您可以执行某种类型的爬山算法来找到中心。
当然，这些 n 个椭圆不一定是圆，所以只选择离中心最近的点可能行不通，但可能是一个很好的近似值。
你或许可以对这 20 个点(如果它们是固定的)进行一些预处理，以找出一个好的分区方案(基于以上信息)。
希望对您有所帮助。
关于algorithm - 找到与其他点集的距离总和最小的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4609846/