查找点距离之和来设定其他点的是最小的

我点的一组（X）（不是很大比方说1-20分），第二（Y），更大的点的集合。我需要从Y中选择一些点到的距离总和从X的点数是最小的。查找点距离之和来设定其他点的是最小的

，我想出了一个主意，我会像对待X为多边形的顶点，找到这个多边形的重心，然后我会选择从最接近重心Y上点。但我不确定质心是否最小化它到多边形顶点的距离的总和，所以我不确定这是否是一种好方法？有没有解决这个问题的算法？

点由地理坐标定义。

来源

2011-01-05 Pawel Markowski

您是指曲面上的经纬度，还是平面上的x-y？ – 2011-01-05 22:31:56

质心不会最小化到顶点的距离总和。例如，如果Torricelli三角形点（http://en.wikipedia.org/wiki/Torricelli_point）是最佳的。 – adamax 2011-01-06 14:48:31

质心的多边形的可能不是正确的，但是这样的点存在。

在纸：n-ellipses and the minimum distance problem，它表明，如果点（称为焦点，你的X集）不共线，然后

存在对和的独特之处（称为中心）的距离最小化。这一点是这样的，从该点到焦点的单位矢量之和为零！
点的轨迹为其中距离的总和是恒定的为凸曲线（称为正椭圆形）包含中心
的n椭圆为距离d完全包含该正椭圆为D'的任何其他距离D'< D.

因此，您可以执行某种类型的爬山算法来查找中心。

当然这些正椭圆不一定圆，所以刚采摘点最接近中心可能无法正常工作，但可能是一个很好的近似。

你也许可以对20个点进行预处理（如果这些点是固定的），找出一个好的分区方案（基于上述信息）。

希望有所帮助。

来源

2011-01-06 03:43:14

我认为不需要模拟退火。因为这里只有一个当地的最小值，所以可以进行简单的爬山。 – adamax 2011-01-06 14:45:19

@adam：是的，我的意思是爬山（与这些:-)失去联系）。谢谢，会编辑。 – 2011-01-06 18:04:53

如果你希望尽量减少距离（不是距离的总和）的平方和，那么该总和最小的点是点的十

证明平均：

sum(squares of distances) = (x-x0)^2 + (y-y0)^2 + (x-x1)^2 + (y-y1)^2 + ... 

d/dx sum(squares of distances) = 2(x-x0) + 2(x-x1) + ... = 2(Nx - x0 - x1 - ...)

当导数为零，这时候Nx = x0+x1+...发生，所以x = (x0+x1+...)/N

的衍生物是围绕这一点对称，而且功能平方之和最小，所以我敢肯定最接近POIN在Y这个平均点是最好的。

最小化的距离是很难的，但我怀疑相同的算法，在您测试，也将工作设定伊苏的更大的回旋余地。

来源

2011-01-06 01:39:51

我不认为你用通常的方式使用了平方和。如果我们谈论的是一个有效的度量，那么任意两点之间的距离将总是大于或等于0. – Samsdram 2011-01-06 01:46:01

我的意思是平常的平方和度量，它总是> = 0。什么让你认为它不是' T' – 2011-01-06 02:49:33

我的观点与数学的说明清晰度有关。 OP要求Y中的点将该点与X中的点之间的距离之和最小化。尽管OP没有指定距离度量，例如您称之为平方和的欧几里得范数。假设尽管OP要求Y中的点使Y中的点与X中的点之间的平方距离之和最小，那么空间平均值将不是可行的解决方案。 – Samsdram 2011-01-06 03:37:43

因为要距离中的最小总和我相信你可以的点集X的减少了空间的意思。然后，您可以使用KDTree或某种空间分区树来查找Y最接近X的空间平均值的点。使用空间分区树可以比检查所有可能的点节省很多工作量。

来源

2011-01-06 01:44:31 Samsdram

对不起，我暗示暴力。问题提出的方式我们不知道X，Y在哪里。假设X是30分，Y是1000分。然后对于Y和30个距离的每个点。总共30000个计算，在jiffy中完成。这保证了最低限度。找到X的一些“中心”并选择最接近的Y将只是一个近似的解决方案。

更有趣的问题是单独为X找到这样一个点。忽略Y. 对于X三点，Fermat-Torichelli点解决了这个问题。

来源

2016-07-17 07:05:44 user6599366

查找点距离之和来设定其他点的是最小的

回答

相关问题