algorithm - 在给定的一组点中找到最近的一对点

Question

Q) 在给定的一组点中找到最近的一对点。

预期时间复杂度：O(n log2(n)) / O(n log(n))

我正在从这里阅读这个问题。但是我无法理解一些事情：

1. 我们通过 Y 对已经按 X 排序的点进行排序来实现什么？

2. 当我们从其中一个半场中取一个点时，我们不会错过一些案例吗？即，如何取中点确保形成的条带包含所有候选点，其距离小于两个递归调用返回的距离？

3. 即使证明了上述点，我们是否应该取两半的中点，即左半边的m和右半边的(m+1)？

标签： algorithmdata-structuresgeometrycomputational-geometryclosest-points

Answer 1

2）您使用中点的 x 坐标找到将点一分为二的线。递归调用比较所有不越过该线的对，因此剩下的就是比较确实越过该线的对。如果两点之间的距离小于d ，并且它们位于直线的任一侧，那么它们距离直线的距离都必须小于d 。

3）嗯，这将在递归调用中完成。我不知道你还有什么意思。

1）条带中的点被分离出来并排序。然后，给定条带中的一个点，所有 y 坐标在d内的点都在它周围的一个连续区域中。这些是您唯一需要与之比较的其他点，并且排序使您可以快速轻松地找到这些点。该算法的神奇之处在于，任何此类区域中可能的点数都严格限制为一个常数值。这是因为（由递归调用确定）直线两侧没有任何一对点比d更近。