最近的点对

Question

在http://en.wikipedia.org/wiki/Closest_pair_of_points_problem中提到，在另一半上最多有6个点是离其他点最近的，可以用下面的图表示： 我的问题是对于P1和P2点，它们距离红点的距离将超过sqrt(2)*d，为什么它们还是解的一部分？为什么最多只有4个点离P最近而不是最多6个点呢？谢谢。

- william007

Answer 1

P1和P2不是解决方案的一部分，但它们必须在寻找解决方案的过程中进行检查，因为算法会检查盒子中的所有点，并且P1和P2都在盒子中。

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

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

• 在右侧线上可能有多达6个点与P的距离小于d。

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

1. 在距P距离小于d的右侧点都在盒子里。
2. 在盒子中可能有多达6个点。

- Gareth Rees

---

如果 "直线右侧可能有最多6个点与 P 的距离不超过 d。" 不成立，那么正确的点数量是多少？如果小于6个点，我们是否可以只检查其中的5个点？ - william007

我认为右半部分距离点P小于d的最大点数实际上是三个。但问题是，我们如何安排仅检查这些点？构建一个数据结构以便我们可以有效地列出盒子内的点相当容易，但哪种数据结构适合圆形段呢？ - Gareth Rees

谢谢你的帮助，我不确定是否可以问一个与问题不太相关的问题：请问您用什么软件绘制图表？看起来很不错 :) - william007

嗨，Gareth，如果我想在Windows 7上绘制类似的图形，你有推荐的图形绘制软件吗（例如Mac上的OmniGraffle）？ - william007

如果我们将盒子中的点数量严格减少到小于d会怎样呢？这样，盒子中只有3个点彼此之间距离为d。 - Danilo Souza Morães

Answer 2

我们只计算可以位于右侧 d x 2d 矩形中的最大点数。由于任意两个点的最小距离为 d，因此我们最多可以在满足此约束条件的情况下在矩形中放置 6 个点，如图所示。

请注意，右侧距离 P 不到 d 的点应全部位于以 P 为圆心、半径为 d 的圆弧段内。该段落内最多可能有 4 个点。然而，查找圆弧段内点的数量比查找矩形内点的数量更加复杂。因此，我们使用矩形代替，并额外付出查找最多 2 个点的成本。

- krjampani

---

不，您不能有6个距离P在d范围内的点。我已经编辑了帖子以使其更加清晰。希望这可以帮到您。 - krjampani

Answer 3

这个限制只是用于复杂度估计。在代码中，你可以在距离dRmin内上下扫描。这个限制表明，在每次这样的扫描中最多只会看到6个点，使得时间复杂度为O(1)。

- goodwind89