algorithm - 在最近的点对分治算法中，按点的y值对“条”进行排序有什么意义？

Question

我相信我非常清楚地了解该算法，除了您通过查看分区来查看是否有任何接近的点并创建一个条带，其中条带内的点是候选点的步骤。

但随后该算法规定按它们的 y 坐标对点进行排序，然后检查条带中的其他点以查找是否存在比先前找到的距离更小的距离。这基本上听起来像是你在地带内的蛮力。

例如，以下是《算法导论》所述：

因此，您似乎只是将每个点与所有其他点进行比较以找到最接近的点？那为什么要按y值排序呢？您已经按 x 对它们进行了排序，为什么不用蛮力呢？

Answer 1

您不会蛮力与 中的所有点进行比较，Y'而仅与 . 旁边的点进行比较p。如果那个已经太远了，你可以停下来，因为所有其他点都会更远。如果最后一个仍在您的搜索距离内，您只会继续评估下一个最近的邻居。

文本在“我们将很快看到”部分对此进行了解释。

排序是这里的一种优化，允许您O(1)在支付O(n log n)一次排序成本后迭代最近的邻居。