找到离其他点最近的点

Question

9

给定N个点（在二维平面上）的x和y坐标。您需要找到一个点P（在N个给定的点中），使得其他所有（N-1）个点到P的距离之和最小。

例如，给定N个点p1（x1，y1），p2（x2，y2）... ... pN（xN，yN）。我们需要从p1，p2 ... PN中找到一个点P，其余所有点与它的距离之和最小。

我使用了暴力方法，但我需要更好的方法。我还尝试了找中位数、平均数等方法，但并不适用于所有情况。

然后我想到了一个办法，将X视为多边形的顶点，并找到该多边形的重心，然后我会选择离重心最近的Y中的一点。但我不确定重心是否将其与多边形顶点的距离之和最小化，因此我不确定这是否是一个好方法？是否存在解决此问题的算法？

- kamal

一种针对暴力算法的优化方法是计算距离的平方而不是距离本身。这是因为计算平方根是一项非常昂贵的操作。 - K Mehta

2

@KshitijMehta 优化平方距离的和并不等同于优化距离的总和。 - Ivaylo Strandjev

嘿，程序员，我相信我已经想出了一种算法来解决这个问题。它相当复杂，可能需要几天时间才能发布一个合适的答案解释。如果你还有兴趣，请告诉我... - Cephron

现在，我会先给出这个提示... 它涉及将数据点分组成网格，并反复将单元格细分为更小的单元格 :) - Cephron

3个回答

2

如果您的点分布得很好，而且如果点的数量太多以至于暴力计算（计算每个点到其他每个点的总距离）不可行，那么以下方法可能会给您一个足够好的答案。所谓“分布得很好”，是指（大致）均匀或（大致）随机分布，且没有在多个位置上有明显聚集。

在空间中创建一个均匀的k*k网格，其中k为奇数。如果您的点分布得很好，那么您要寻找的点（可能）就在此网格的中心单元格中。对于网格中的所有其他单元格，统计每个单元格中的点数，并近似计算每个单元格中点的平均位置（可以使用单元格中心或计算单元格中点的平均(x,y)值）。

对于中心单元格中的每个点，计算其与中心单元格中的每个其他点之间的距离，以及其与其他单元格中的点的加权平均距离。当然，这将是从该点到其他单元格中点的“平均”位置的距离，根据其他单元格中点的数量进行加权。

您需要权衡增加k值的精度和增加计算负载之间的关系，并找出适合您点的最佳方法。如果单元格内点的分布远非均匀，则此方法可能不适用。

这种方法在具有重力和电荷等特性的大规模模拟中被广泛使用。但是否适合您的需求，我不知道。

- High Performance Mark

0

我不确定我是否理解您的问题，但当您计算最小生成树时，从树上的任何一个点到另外任何一个点的路径之和是最小的。

- Micromega

2

你需要将一个点到其他所有点的距离之和最小化。最小生成树可以计算出构建边缘所需的最小距离总和，以便从任何一点到达任何其他点。但这不是OP所要求的。 - Ivaylo Strandjev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sajal Jain · Accepted Answer

需要考虑的点被称为几何中位数。

重心或质心与几何中位数类似，被定义为将每个样本距离的平方和最小化的点。它可以通过一个简单的公式找到——它的坐标是样本坐标的平均值，但是对于几何中位数，没有这样的公式，而且已经证明一般情况下不存在只涉及算术运算和k次根的显式公式或精确算法。