为什么我们在最近对算法中最多比较7个点？
因此,如果在δ*2δ矩形R内,我们只需要比较从左侧的一个点到右侧的7个点.我不明白的是,尽管阅读了证据,但是在R里面,我们可以在矩形内填充尽可能多的点,这可能超过7的总数.想象一下,如果我们有δ= 2,点p(1.2, 1.1)在左侧,在右侧,我们有一大堆q,如q(1.5,1.7),q(1.4,1.3),.....怎么只能比较7点检测到最近的一对？我认为如果是这种情况,我们必须比较矩形R中的每个点.请帮我.
Mig*_*Mig 11
你的矩形内部可能只有6个点,因为这是你可以放入一个带有sides\delta和2*\delta的矩形的最大点数,它们保持了它们至少彼此相距的delta的属性.
下面显示了这6点的方法如下图所示:
您可以检查自己是否有办法在矩形内放置另一个点而不违反距离属性.如果你添加超过6个点,它们将小于\ delta,这是一个矛盾,因为\ delta应该是最近的一对之间的距离.
由于最多可能有6个点,因此测试7将保证您找到解决方案.
我从这些UCSB幻灯片中得到了图1,这可能对您有用.
- 突然我明白了.R中的所有对都必须是delta,因为如果它小于delta,那么这对必须是delta.这意味着矛盾,因为delta应该是最后一步之前的最小距离,这意味着我们在查找delta时的算法在实际实现中是错误的.如果你添加这个,我会标记为正确的答案.该死的,这个隐藏的知识花了我很多时间来弄明白. (4认同)
- @Amumu就是这样！我添加了关于矛盾部分的简短解释，以供将来参考。 (2认同)