给定一个二维点列表，找到距离所有其他点最近的点。

Question

给定一个二维点列表，找到距离所有其他点最近的点。

7

Input: list of 2d points (x,y) where x and y are integers.

Distance: distance is defined as the Manhattan distance. 
    ie:
    def dist(p1,p2) 
         return abs(p1.x-p2.x) + abs(p1.y - p2.y)

如何高效地找到距离其他所有点最近的点？

我只能想到一个暴力的O(n^2)解法：

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)

基本上看每一对点。

- Razor Storm

这不是欧几里得距离，你需要对每个 (p1.x - p2.x) 和 (p1.y - p2.y) 进行平方，并对总和取平方根。方法 dist() 是曼哈顿距离。 - amit

哎呀，我本来不是想用欧几里得距离的。我会进行编辑。 - Razor Storm

3个回答

4

你需要的是质心。将所有x和y相加，再除以整个系统的质量即可。现在，假设你有一些质量相同的粒子，它们的质量为1。然后，你只需要将这些粒子的位置相加，再除以粒子数即可。比如，我们有p1(1,2)、p2(1,1)、p3(1,0)。

// we sum the x's 

    bestXcord = (1+1+1)/3 = 1

//we sum the y's 

    bestYcord = (2+1)/3 = 1

所以p2是最近的。

在O(n)时间内解决。

- raam86

2

并非如此。重心不一定是集合中的一个点，而要求指定点必须来自于集合。例如，(0,2),(0,0) - 你不能选择 (0,1) 作为答案。我猜最靠近重心的点就可以-但你能证明吗？ - amit

我同意它并不完美。但是这个相关性如此美妙，以至于我不得不将其作为答案。 - raam86

再想一想，不行——肯定不行。考虑：(0,0),(0,0),(0,0),(5000,0),(10000,0)。15,000/5=3,000。最接近的是(5000,0)，到它的距离之和为20,000。而如果选择(0,0)，则距离之和将为15,000。 - amit

1

只有在近似平坦的分布中，质心参数才有效 - 例如在环形上会出现问题（质量分布的微小差异使得许多内部点中的一个成为最佳点）。 - Eugen Rieck

我们仍然可以使用该算法来获取最接近的实际点。再次检查这些点，寻找存在的最接近值。 - raam86

显示剩余4条评论

1

从您的初始算法开始，存在一种优化可能：

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
        //This will weed out bad points rather fast
        if dist>=minDist then continue(p1)
    /*
    //Unnecessary because of new line above
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)
    */
    bestPoint = p1

这个想法是尽快丢弃异常值。这可以进一步改进：

使用启发式“内部”点开始p1循环（这将创建一个良好的minDist，因此更差的点会更快地被丢弃）
使用启发式“外部”点开始p2循环（这使dist快速上升，可能更快地触发退出条件）

如果你为了速度而牺牲大小，你可以选择另一条路：

//assumes points are numbered 0..n
dist[]=int[n+1]; //initialized to 0
for (i=0;i<n;i++)
  for (j=i+1;j<=n;j++) {
    dist=dist(p[i], p[j]);
    dist[i]+=dist;
    dist[j]+=dist;
  }
minDist=min(dist);
bestPoint=p[argmin(dist)];

这需要更多的空间来存储dist数组，但每个距离只计算一次。这有利于更适合“获取N个最佳点”类型的问题和计算密集型度量。我怀疑在x86或x64架构上，对于曼哈顿度量来说并没有什么好处：内存访问将严重占主导地位。

- Eugen Rieck

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

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

- krjampani · Accepted Answer

注意，在一维中，最小化到所有点距离之和的点是中位数。

在二维中，该问题可通过以下方法在 O(n log n) 时间内解决：

创建一个按 x 坐标排序的数组，并为数组中的每个元素计算选择该坐标的“水平”成本。元素的水平成本是投影到 X 轴上所有点之间的距离总和。这可以通过两次扫描数组（从左到右和从右到左）在线性时间内计算得出。同样地，创建一个按 y 坐标排序的数组，并为数组中的每个元素计算选择该坐标的“垂直”成本。

现在对于原始数组中的每个点，我们可以在 O(1) 的时间内计算到所有其他点的总成本，方法是将其水平成本和垂直成本相加。因此，我们可以在 O(n) 的时间内计算出最优点。因此，总运行时间为 O(n log n)。