在 O(nlogn) 中查找平面中具有非不同 x 坐标的最近点对

Question

我在网上看到的用于查找平面中最近点对的算法的大多数实现都有两个缺陷之一：它们要么不满足 O(nlogn) 运行时，要么不满足适应某些点共享 x 坐标的情况。是否需要散列图（或等价物）以最佳方式解决此问题？

粗略地说，所讨论的算法是（根据 CLRS Ch. 33.4）：

对于点数组 P，创建额外的数组 X 和 Y，使 X 包含 P 中的所有点，按 x 坐标排序，Y 包含 P 中的所有点，按 y 坐标排序。
将点分成两半 - 放下一条垂直线，以便将 X 分成两个数组，X_L 和 X_R，并类似地划分 Y，使得 Y_L 包含线左侧的所有点，Y_R 包含线右侧的所有点，均按y 坐标。
对每一半进行递归调用，将 X_L 和 Y_L 传递给 one 和 X_R 和 Y_R 到另一个，并在每一半中找到最小距离 d。
最后判断分界线左边一个点右边一个点距离小于d的一对；通过几何论证，我们发现我们可以采用对分界线距离d内的每个点只搜索接下来的7个点的策略，即分割子问题的重组是只有一个 O(n) 步骤（即使乍一看 看起来 n²）。

这有一些棘手的边缘情况。人们处理这个问题的一种方法是在每个重组步骤（例如 here）对距离分界线 d 的点带进行排序，但已知这会导致O(nlog²n)解.

人们处理边缘情况的另一种方法是假设每个点都有一个不同的 x 坐标（例如 here）：请注意 closestUtil 中添加到 Pyl（或 Y_L 如我们所说）如果 Y 中某点的 x 坐标 <= 直线，否则为 Pyr (Y_R)。请注意，如果所有点都位于同一条垂直线上，这将导致我们在 C++ 中写入超过数组的末尾，因为我们将所有 n 点写入 Y_L.

因此，当点可以具有相同的 x 坐标时，棘手的一点是将 Y 中的点划分为 Y_L 和 Y_R取决于 Y 中的点 p 是否在 X_L 或 X_R 中。 CLRS 中的伪代码是（为简洁起见略作编辑）：

for i = 1 to Y.length
    if Y[i] in X_L
        Y_L.length = Y_L.length + 1;
        Y_L[Y_L.length] = Y[i]
    else Y_R.length = Y_R.length + 1;
        Y_R[Y_R.length] = Y[i]

但是，如果没有伪代码，如果我们使用的是普通数组，我们就没有可以在 O(1) 时间内确定 Y[i] 是否在 X_L 中的魔术函数。如果我们确信所有 x 坐标都是不同的，当然 - 我们知道 x 坐标小于分界线的任何东西都在 X_L 中，所以通过一次比较我们知道将 Y 中的任何点 p 划分成什么数组。但是在 x 坐标 不一定 不同的情况下（例如，在它们都位于同一条垂直线上的情况下），我们是否需要哈希映射来确定一个点是否在Y在X_L或X_R中成功分解Y为Y_L和Y_R 在 O(n) 时间内？或者有别的策略吗？

Answer 1

是的，这里至少有两种方法。

首先，正如 Bing Wang 所建议的，是应用轮换。如果角度足够小，这相当于在用 x 比较后用 y 坐标打破平局，不需要其他数学运算。

二是调整G4G上的算法，使用linear-time分区算法划分实例，linear-time排序合并征服实例。大概没有这样做是因为在大多数编程语言中，相对于前面提到的算法，作者更看重排序的简单性。

在 O(nlogn) 中查找平面中具有非不同 x 坐标的最近点对

Finding closest pair of points in the plane with non-distinct x-coordinates in O(nlogn)

algorithm

geometry

closest-points