有什么不对我的逻辑分而治之的最近点对问题的算法？(What is wrong with my log

我一直在关注Coursera对算法当然并与有关最接近的对问题分/治算法的思想来了，我想澄清。

按照拉夫加登教授的算法（你可以看到这里 ，如果你有兴趣）：对于给定的点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. 让增量是DIST（P1，Q1）和DIST的最小值（P2，Q2）
5. 这是不幸的情况下，让P3，Q3是closestSplitPair（PX，PY，三角洲）
6. 返回最好的结果

现在，我想澄清有关第5步。我应该说这事前，什么我建议，是几乎没有任何进步可言，但如果你还有兴趣，预读。

ř教授表示，由于点在X和Y方向已经排序，以找到最佳的一对在步骤5中，我们需要遍历个宽度2 *增量的带材，从底部开始向上，并在内部循环中，我们只需要7 comparisions。 这能做得更好，只是一个？

我怎么觉得是可能似乎有点困难明文解释，所以我画了一个图，并写在纸上，并在这里上传吧：

由于没有其他人想出了就是，我敢肯定有一个在我的思路的一些错误。 但我从字面上一直在想这个好几个小时，现在，我不得不张贴此。 这一切是在我的脑海。

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

Answer 1:

你的子弹点＃5结论不正确。 试着画点A接近分界线。

可以具有不是彼此的增量内A的增量内的两个点（一个上面，下面的一个）。

  | B
  | 
 A|
  | 
  | C

这里， dist(A,B) = dist(A,C) < dist(B,C)

这就是为什么图片是有帮助的，以获得直觉一个完美的例子，但证据仍然是必要的备份你的结论。

文章来源: What is wrong with my logic for the divide and conquer algorithm for Closest Pair Problem?