在寻找最接近的对点时对这七点的解释
我试图掌握各种文献中最接近对点问题的解释。虽然它们的基本方法是相同的，分而治之-合并(分而治之)，得到线性时间合并(合并/征服)，实际的实现是微妙的不同的文章和书籍。
线性时间合并是这里的关键，它试图限制要比较的点数。
在克莱恩伯格书中考虑点的方式与在这个维基百科文章或科门书中考虑点的方式有点不同。
无论如何，对于后两个问题，我们找到了关于被认为是这里和这里的点数的很好的解释，包括许多其他的。
对于手头的问题，请查看这些幻灯片 (幻灯片32)的克莱恩伯格书。11 point gap的说法也是如此。更详细的解释可以在第6页第6.2.5.6节找到这里。
然而，在上述幻灯片的同一页(幻灯片32)中，我们发现了这样的说法：“如果我们用7替换12，仍然是正确的。”
我未能找到对上述索赔的解释。
请看下图，
如果我们把红点和右半边的比较，右边的点应该在阴影的半圆中。我已经试过把极端的放在蓝色里了。但是，它们之间的距离是5-(-2)|+1=8，5-15 x+1= 11。
我可能在这里失踪了什么？
回答 3
Stack Overflow用户
发布于 2013-10-26 08:51:02
实际上，你不需要计算下半个点的距离，因为在你的范围内，如果你考虑按y轴排序的点，那么你从底部开始，只考虑上面区域中的点。
Stack Overflow用户
发布于 2013-03-27 20:31:23
你可以在网格上加9分。如果(0,0)是中心，假设是delta=1，你可以在(-1，-1)，(-1,0)，.，(1,1)有9个点。
证明它最多只有9：
即使在最佳的包装，你只能有3层的圆圈，每一个半径(1/2)，所有的中心在一个2X2平方。
所以，在这之后，差降到了8。为了达到七，你必须假设它不是特例(我忘记了它的技术术语，但它在计算几何中是一个流行的假设。它还指出，3点不能在同一条线上。它被称为“一般性假设”或类似的东西。
Stack Overflow用户
发布于 2021-10-11 14:13:27
根据CLRS 33.4：
第1行左边有2点(见最左的2点)，2指向第1行的右边(见最右的2点)，第1行的4点( PL和PR都在相同的点上)。
2 + 2 + 4 = 8
不包括自我，所以是8 - 1 = 7
例如，我们正在计算PL (l上的上点)与其他点之间的距离，让我们逆时针计算：
- 第一点(PL)是最左边的，
- 第二(PL)是左下角，
- 3 (PL)是l的底部，
- 4 (PR)也是l的底点，
- 5 (PR)是右下角，
- 6 (PR)是右上角，
- 第7 (PR)是l上的上点。
https://stackoverflow.com/questions/15664962
复制相似问题
腾讯云开发者
