我对最近点对问题使用分治算法的逻辑有什么问题？

Question

我一直在跟进Coursera的算法课程，并对最接近点问题的分治算法产生了疑问，希望得到澄清。

根据Roughgarden教授的算法（如果您感兴趣可以在这里看到）： 对于给定的点集P，我们有两个副本 - 按X和Y方向排序的Px和Py。该算法可表示为

closestPair(Px,Py)：

1.将点分成左半部分Q和右半部分R，并沿着x和y方向形成两个有序的副本-Qx、Qy、Rx、Ry 2.令closestPair(Qx,Qy)为点p1和q1 3.令closestPair(Rx,Ry)为p2,q2 4.令delta为dist(p1,q1)和dist(p2,q2)的最小值 5.这是不幸的情况，让p3,q3成为closestSplitPair(Px,Py,delta) 6.返回最佳结果

现在，我想要澄清的是第五步相关的内容。需要事先说明的是，我所提出的改进几乎没有什么改善作用，但如果您仍然感兴趣，请继续阅读。

R教授说，由于点已经按X和Y方向排序，为了在第5步中找到最佳对，我们需要遍历宽度为2*delta的条带上的点，从下到上开始，在内循环中只需要7次比较。这个过程能否优化到只需要一次？

我认为可能有一种方法，但用纯文本解释有些困难，所以我画了一个图并将其写在纸上上传到了这里：

既然没有其他人提出来，我相当确定我的思路中存在一些错误。但我已经想了几个小时了，我必须发帖。这就是我脑海中的全部内容。

有人能指出我哪里错了吗？

- Programming Noob

Answer 1

您在第五点总结是不正确的。试着将A点靠近分界线。

您可以有两个在A点附近（一个上面，一个下面）且彼此之间不在delta范围内的点。

  | B
  | 
 A|
  | 
  | C

这里，dist(A,B) = dist(A,C) < dist(B,C)。这是一个完美的例子，说明图片有助于获得直觉，但证明仍然是支持结论的必要条件。

- tskuzzy

---

你关于我在第5点结论错误的看法是正确的。半径为delta的同一圆中的两个点可能相距超过delta单位。然而，在这种情况下，一个点将在考虑点下方，另一个点在上方，就像你指出的那样。由于我们是从下往上走，在垂直条带中按y坐标递增的顺序考虑点，我们不需要检查与考虑点下方的点的距离，对吧？在你的例子中，当我考虑A时，我不会检查C与A之间的距离，因为（续..） - Programming Noob

因为在考虑 A 之前，我已经考虑过 C，并且在那段时间里，我一定检查了 C 和 A 之间的距离。所以为了找到最小距离，仍然只需要考虑比当前点高的一个点，对吗？ - Programming Noob