我正在查看维基百科条目以了解如何解决此问题。它列出了五个步骤
1.沿x坐标排序点
2.用一条垂直线x = xmid将点集分成两个大小相等的子集
3.在左右子集中递归求解。这将分别给出左侧和右侧的最小距离 dLmin 和 dRmin。
4.求一对点之间的最小距离dLRmin，其中一个点位于分界线的左侧，第二个点位于右侧。
5.最终答案是dLmin、dRmin和dLRmin中的最小值。
第四步我很难理解。如何选择线左侧的点与线右侧的点进行比较。我知道我不应该比较所有点，但我不清楚如何选择要比较的点。请不要给我发链接，我已经搜索了很多链接，但没有找到可以帮助我理解第 4 步的解释。
谢谢
亚伦
您的问题的答案在维基百科文章的下一段中：
事实证明，步骤 4 可以在线性时间内完成。同样，一种简单的方法需要计算所有左右对的距离，即在二次时间中。关键观察基于点集的以下稀疏特性。我们已经知道最近的一对点的距离不超过 dist = min(dLmin,dRmin)。因此，对于分割线左侧的每个点 p，我们必须比较与分割线右侧尺寸为 (dist, 2 * dist) 的矩形中的点的距离，如图所示。更重要的是，这个矩形最多可以包含 6 个成对距离至少为 dRmin 的点。因此，在步骤 4 中最多计算 6n 个左右距离就足够了。
我认为我不能比他们已经说得更清楚了，但是您对算法的这一步有什么具体问题吗？