最近对点(Closest pair of points)

在http://en.wikipedia.org/wiki/Closest_pair_of_points_problem我们可以看到，它提到，至多6个点中的最接近的另一半的点，这可以被表示为下面的图：

我的问题是点P1和P2点，以红点的距离将超过开方（2）* d，为什么它是解决方案的一部分？ 为什么它不是最多4点最接近为P，而不是在6分？ 谢谢。

Answer 1:

P1和P2不是解决方案的一部分，但他们在途中解决方案进行审查，因为算法检查在框中的所有点，P1和P2是在箱子里。

请注意，没有这样的点作为您的Q能够存在，因为假设点之间的最小距离在右半图的是d。

编辑补充：您似乎认为，维基百科的文章正在这样的要求：

• 可能有多达6个点上是P的距离d内的线的右侧。

这种说法是错误的。 但文章并没有提出这样的要求。 相反，它使两个独立的权利，这两者都是正确的：

1. 所有在是P的距离d内的线的右侧的点是箱内。
2. 可能有高达箱6分。

Answer 2:

绑定的是复杂性估计唯一重要的。 代码明智的，你可以简单地扫描并距离dRmin内上下。 这里的束缚建议你最多在每个这样的扫描见6分，使得这个O（1）。

Answer 3:

我们只计算可位于右侧DX 2D矩形点的最大数量。 由于任何两个点被限制为具有d的最小距离，我们可以在矩形放置至多6个点，同时满足该约束，如该图所示。

注意，是d距离内选自P，关于右侧的点应位于所有以P为中心的圆的圆形段内且半径为d。 有可能在这一领域最高4分。 然而，在一个段内发现的点的数量大于一矩形内找到的点的数量更复杂。 所以我们用矩形来代替，而招致其搜索最多2个额外点的额外费用。

文章来源: Closest pair of points