algorithm - 为什么我们在最近对算法中最多比较 7 个点？

Question

所以，如果在δ * 2δ矩形R内，我们只需要比较左边的一个点和右边的7个点。我不明白的是，尽管阅读了证明，但在 R 内部，我们可以在矩形内填充任意数量的点，这可能会超过 7 的总数。想象一下，如果我们有 δ = 2，一个点 p(1.2, 1.1) 在左边，在右边，我们有一大堆q，比如q(1.5, 1.7) , q(1.4, 1.3),.....怎么只比较7个点就能检测到最近的一对？我认为如果是这种情况，我们必须比较矩形 R 内的每个点。请帮助我。

Answer 1

您的矩形内可能只有 6 个点，因为这是您可以在边长为 δ 和 2δ 的矩形中放置的最大点数，同时保持它们彼此至少相距 δ 的属性。

这6个点的铺设方式如下图所示:

您可以自己检查是否有办法在不违反距离属性的情况下将另一个点放在矩形内。如果你添加超过 6 个点，它们之间的距离将小于 δ，这是一个矛盾，因为 δ 应该是最近的对之间的距离。

由于最多可能有 6 个点，测试 7 个将保证您找到解决方案。

我得到图1来自 these UCSB slides ，这可能对您有用。