algorithm - 这七个点在寻找最近的点对的解释

Question

我试图掌握各种文献中最近对点问题的解释。尽管它们的基本方法都是相同的，即分而治之（分而治之）和线性时间合并（合并/征服），但实际实现在文章和书籍之间略有不同。

线性时间合并是这里的关键，它试图限制要比较的点数。

Kleinberg 书中考虑点的方式与这篇Wikipedia 文章或Cormen 书中考虑点的方式有点不同。

对于手头的问题，请查看Kleinberg book的这些幻灯片（幻灯片 32）。的声明在同一张幻灯片中。更详细的解释可以在第 6 页第 6.2.5.6 节中找到。11 point gap

然而，在上述幻灯片的同一页（幻灯片 32）中，我们发现类似“如果我们将 12 替换为 7 仍然正确”的声明。

我未能找到对上述主张的解释。

请看下图，

在此处输入图像描述

如果我们考虑将红点与右半部分的点进行比较，则右半部分的点应该在阴影半圆中。我试图把极端的放在蓝色。它们仍然是 |5-(-2)|+1 = 8 和 |5-15|+1 = 11。

我可能在这里错过了什么？

score 1 · Accepted Answer

实际上，您不需要计算下半部分点的距离，因为在您的范围内，如果您考虑根据 y 轴排序的点，那么您从底部开始，只考虑其上方区域中的点。

score 0 · Accepted Answer

实际上，您可以在网格上放置 9 个点。如果 (0,0) 为中心并假设 delta=1，则在 (-1,-1)、(-1,0)、...、(1,1) 处可以有 9 个点。

证明它最多只有 9：

即使在最佳包装下，您也只能有 3 层圆，每个圆的半径为 (1/2)，所有中心都在 2X2 正方形内。

因此，在此之后差异下降到 8。要达到七，你必须假设它不是一个特殊情况（我忘记了它的技术术语，但它是计算几何中的一个流行假设。它还指出 3 个点不能在同一条线上。它被称为“一般性假设”或类似的东西。

score 0 · Accepted Answer

根据CLRS 33.4：

l 线左边有2个点（见最左边的2个点）， l线右边有2个点（见最右边的2个点），l线有4个点（PL和PR都开相同的点）。

2 + 2 + 4 = 8

不包括自我，所以它是8 - 1 = 7

例如，我们正在计算 PL（l 上的上点）和其他点之间的距离，让我们逆时针计算：

3 回答 3