algorithm - 最近的一对点

Question

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

我的问题是针对点 P1 和点 P2，到红点的距离会超过 sqrt(2)*d，为什么它是解决方案的一部分？为什么最接近 P 的不是最多 4 个点而不是最多 6 个点？谢谢。

Answer 1

P1和P2不是解的一部分，但必须在求解的过程中对其进行检查，因为算法会检查框内的所有点，而P1和P2都在框内。

请注意，不存在像您的Q这样的点，因为根据假设，图表右半部分的点之间的最小距离是d。

编辑添加：您似乎认为维基百科文章正在提出这样的声明：

• 直线的右侧可能有多达 6 个点位于P的距离d内。

这种说法是错误的。但这篇文章并没有提出这样的主张。相反，它提出了两个独立的声明，这两个声明都是正确的：

1. 直线右侧与P距离为d的所有点都在框内。
2. 方框中最多可能有 6 个点。

Answer 2

我们只计算可以位于右 dx 2d 矩形中的最大点数。由于任意两点的最小距离都被约束为 d，所以在满足这个约束的同时，我们最多可以在矩形中放置 6 个点，如图所示。

请注意，右侧距 P d 距离内的点都应位于以 P 为中心且半径为 d 的圆的圆弧段内。该段最多可以有 4 个点。但是，查找线段内的点数比查找矩形内的点数更复杂。所以我们使用矩形来代替，并产生额外的成本，最多只能搜索 2 个额外的点。

Answer 3

界限只对复杂度估计很重要。代码方面，您可以简单地在距离 dRmin 内上下扫描。这里的界限表明您在每次这样的扫描中最多会看到 6 个点，这使得这个 O(1)。