说明在寻找最接近的一对点

我试图把握最接近点对问题的各种文献的解释这七个点。虽然基本的方法都是一样的，但是分而治之（分而治之），并且得到线性时间合并（合并/征服），实际的实现在文章和书籍之间略有不同。说明在寻找最接近的一对点

的线性时间合并在这里关键它试图限制点的数量进行比较。

在Kleinberg book中考虑点的方式与Wikipedia article或Cormen book中考虑点的方式有所不同。

无论如何，对于后面两个，我们可以找到很好的解释点数here和here，包括许多其他。

对于手头的问题，请查看的these slides（幻灯片32）。 11 point gap的索赔处于同一张幻灯片中。更详细的解释可以在第6页的第6.2.5.6节中找到here。

但是，在above mentioned slides（幻灯片32）的同一页面中，我们发现类似于的声明“如果我们用7替换12，则仍然如此。”

我并没有发现上述要求的解释。

请参见下图，

enter image description here

如果考虑到红点与那些在右半部分，分在右半部分进行比较，应在阴凉半圈。我试图把极端的置为蓝色。它们仍然是| 5 - （ - 2）| +1 = 8和| 5-15 | +1 = 11。

这是什么我可能会在这里失踪？

2013-03-27 Masroor

有趣的问题。你介意加入一个简短的入门款给予一定的情境？ – NPE 2013-03-27 17:12:26

增加顶部的几行，希望这满足了目的。 – Masroor 2013-03-27 17:23:41

真棒，谢谢。 – NPE 2013-03-27 17:24:04

实际上你可以在网格上放9个点。如果（0,0）为中心并假定delta = 1，则可以在（-1，-1），（ - 1,0），...，（1,1）处有9个点。

证明，只有在9：

即使在最佳的包装，你只能有一个半径（1/2）用2X2正方形内所有中心的每个圆圈的3层。

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

2013-03-27 20:31:23 ElKamina

你介意稍微说一说最后一部分吗？寻找“一般性假设”没有任何回报。我很想理解这一点。 – Masroor 2013-03-29 05:00:04

@MMA在这一刻我找不到任何参考。假设一般情况下，没有三个点在一条线上，并且在一个平面上没有4个点，而在n超平面上没有n + 1个点。 – ElKamina 2013-03-29 15:44:11

其实你并不需要计算距离的点的下半部分，因为在你的范围内，如果你按Y轴考虑分拣点，那么你从底部开始，上去考虑它上面仅区域的点。

2013-10-26 08:51:02 happs

回答