最近邻对分治算法的故障理解

Question

我刚开始编程，今天我完成了二维空间中最近对问题的简单解法。（2个用于环路）

然而，我放弃了在O（n log n）中找到任何能解决这一问题的方法。即使在研究了它之后，我仍然不明白这怎么能比琐碎的方法更快。

我理解的是:->首先，我们将数组分成两半，只考虑X坐标对所有内容进行排序。这可以在n log n中完成。

接下来是递归调用，它们在每一半中“找到两个距离最小的点”。但是在O(n^2)下是怎么做到的呢？根据我的理解，如果不检查每一个点，就不可能找到N/2个点之间的最小距离。

有一个在一维的解决方案，这对我来说绝对是有意义的。经过排序，我们知道两个非相邻点之间的距离不能小于至少两个相邻点之间的距离。然而，这对于二维空间是不成立的，因为我们有一个附加的Y坐标，它可以导致在X轴上不相邻的两点之间的最小距离。

Answer 1

首先，听从用户@evg的建议--这个答案不能代替对算法的全面描述和数学上严谨的分析。

然而，这里有一些让直觉开始的想法：

>

（递归结构）问题说明：

（在一半中找到最近对的结果）
如果在点集的“左”一半中找到了最近对(p,q)，则该对的距离设置了一个上界，该上界设置了围绕半线的走廊宽度，从该上界可以画出一个从左到右的r和s的更近的(r,s)对。如果到目前为止找到的最近距离是“小”的，它会显著减少候选集的大小。由于点是按其x坐标排序的，该算法可以有效地利用信息。所述走廊仍然可以覆盖n点的整个集合，但如果覆盖了，它提供了点集几何形状的信息：每一半的点基本上将沿着一条垂直线对齐。这些信息可以通过算法加以利用--最简单的方法是再次执行算法，但沿着y坐标排序，并将点集减半一条水平线。请注意，以恒定的次数执行任何算法不会改变由O(.)表示法表示的渐近运行时间。

（查找每半个点的接近对）
考虑检查一对点(r,s)，每半个点。已知它们的x和y坐标的差值不应超过到目前为止找到的最小距离d。由递归可知，不可能有比d更接近r、s的点r'、s'（左边r',右边s')。因此，给定一些R，就不可能有来自另一半的“许多”候选者。
想象一个半径D的圆画在R周围。任何距离另一半s比d近的点必须位于该圆内。让它们有几个--然而，每对之间的最小距离仍然至少为d。在半径d的圆内可以分布的点的最大数目，使得每对点之间的距离至少为d为7-考虑边长为d且其中心与圆心重合的正六边形。因此，在递归之后，最多需要将左半部分的每个R与另半部分的最大恒定点数进行检查，这使得递归之后的算法部分在O(N)中运行。
注意，为给定的R寻找配对候选者是一个有效的操作-来自两个半部分的点数已按相同的准则排序。