对于最近对问题的分而治之算法,我的逻辑有什么问题？

Question

我一直在关注Coursera关于算法的课程,并想出了关于最近对问题的分治/征服算法,我想澄清一下.

根据Roughgarden教授的算法(如果你感兴趣,可以在这里看到):对于给定的一组点P,我们有两个副本 - 在X和Y方向排序 - Px和Py,算法可以给出

closestPair(PX,PY):

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

现在,我想要的澄清与第5步有关.我应该事先说出来,我所建议的,几乎没有任何改进,但如果你仍然感兴趣,请提前阅读.

R教授说由于点已经在X和Y方向排序,为了在步骤5中找到最佳对,我们需要迭代宽度为2*delta的条带,从下到上,在内部循环我们只需要7次比较.这可以只改为一个吗？

我的想法似乎有点难以用纯文本来解释,所以我绘制了一个图表并将其写在纸上并在此处上传:

由于没有其他人想出来,我很确定我的想法中存在一些错误.但我现在一直在考虑这个问题,我只是想发布这个.这就是我的想法.

谁能指出我哪里出错了？

Answer 1

你在第5点的结论是不正确的.尝试绘制点A更接近分界线.

你可以在A的三角形(一个在上面,一个在下面)内有两个点,它们不在彼此的三角形内.

  | B
  | 
 A|
  | 
  | C

在这里,dist(A,B) = dist(A,C) < dist(B,C).

这是为什么图片有助于获得直觉的完美示例,但仍需要证据来支持您的结论.