为什么在最近点对算法中我们最多只需要比较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 内的每个点。请帮帮我。

- Amumu

---

我们可以有一个“证明”的链接吗？ - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft 您可以在 Google Books 上查看《算法导论》：http://books.google.com.vn/books?id=NLngYyWFl_YC&printsec=frontcover&hl=vi&source=gbs_ge_summary_r&cad=0#v=onepage&q=closest%20pair&f=false - Amumu

请查看此答案中的链接。它们提供了一个相当不错的参考。特别是来自《算法导论》的图33.11。 - Azolo

我读了那个内容，但仍不清楚7点的事情。我可以在delta区域中填充无限数量的点，以创建无限数量的值小于delta的对。我一定是漏掉了什么。 - Amumu

具体来说，q(1.5,1.7)和q(1.4,1.3)之间的距离小于构造δ所不可能的距离。 - n. m.

Answer 1

你的矩形内最多只能有6个点，因为在边长为δ和2δ的矩形中放置最多6个点，并保持它们之间距离至少为δ的属性。

将这6个点放置的方法如下图所示：

您可以自行验证，在不违反距离性质的情况下，在矩形内添加另一个点的方式是不存在的。如果添加了超过6个点，则它们之间的距离将小于δ，这是一种矛盾，因为δ应该是最近对之间的距离。

由于最多只能有6个点，因此测试7会保证您找到解决方案。

我从这些UCSB幻灯片中获取了图1，可能对您有用。

- Mig

---

谢谢。你的简单解释让事情清晰了一些。然而，在幻灯片中，它说“如果每对点之间至少相距\delta，那么有多少个点可以在R内部？” 幻灯片中的答案是6个点在R内部，而不是在R的边界上。 - Amumu

@Amumu 是的，但他们真正的意思是“在内部或紧贴边界上”。如果您认为答案足够好，应该接受它。=) - Mig

当然可以，但唯一仍然存在的困惑是7个点的常数。我的意思是，我不能在R内放置无限数量的点来创建具有小于\delta距离的无限对。无限可能太多了，但如果我有大约20个距离小于\delta的点，仅测试7个点是否有意义呢？ - Amumu

突然我明白了。R中的每对数据必须相距delta，因为如果它们之间的距离小于delta，则它们本身必须delta。这意味着矛盾，因为在此最终步骤之前，delta应该是最小的距离，这意味着我们在找到delta的算法实现中存在错误。如果您添加了此内容，我将标记为正确答案。该隐藏知识让我花费了相当长的时间才弄清楚。 - Amumu

@Amumu 没错！我添加了一个简短的解释，以备将来参考。 - Mig