我在网上看到的大多数寻找平面中最接近的一对点的算法实现都有两个缺陷之一：要么不能满足O(nlogn)运行时，要么不能适应某些点共享x坐标的情况。是否需要哈希映射(或等效)来优化解决此问题？
粗略地说，所讨论的算法是(根据CLRS第33.4章)：
- 对于点P的数组，创建额外的数组X和Y，使X包含P中按X坐标排序的所有点，Y包含P中按照Y坐标排序的全部点
- 将点一分为二-放下一条垂直线，将X拆分为两个数组，XL和XR，并以类似方式划分Y，使YL包含该线左侧的所有点，YR包括该线右侧的所有点(均按Y坐标排序)
- 对每一半进行递归调用，将XL和YL传递给一个，将XR与YR
- 最后，确定是否存在一对，其中一点在分界线的左侧，一点在右侧，距离小于d；通过几何论证，我们发现我们可以对分割线距离d内的每个点采用只搜索下7个点的策略，这意味着分割子问题的重组只是O(n)步(即使乍一看n2)
这有一些棘手的边缘情况。人们处理这一问题的一种方法是在每个重组步骤(例如这里)对距离分界线d的点带进行排序，但已知这会导致O(nlog2n)解。
人们处理边缘情况的另一种方法是假设每个点都有一个不同的x坐标(例如这里)：注意closestUtil中的片段，如果Y中一个点的x坐标<=或者以其他方式转换为Pyr(YR)。请注意，如果所有点都位于同一垂直线上，这将导致我们在C++中写入数组的末尾，因为我们将所有n点写入YL。
因此，当点可以具有相同的x坐标时，棘手的问题是将Y中的点划分为YL和YR，这取决于Y中的一个点p是在xL还是xR中。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]
然而，如果没有伪代码，如果我们使用普通数组，我们就没有一个神奇的函数可以确定Y[i]在O(1)时间内是否在X_L中。如果我们确信所有的x坐标都是不同的，当然-我们知道任何x坐标小于分界线的东西都在xL中，所以通过一次比较，我们知道将Y中的任何点p划分为哪个数组。但是，在x坐标不一定不同的情况下(例如，在它们都位于同一垂直线上的情况下)，我们是否需要哈希图来确定Y中的点是在xL还是xR中，并在O(n)时间内成功地将Y分解为YL和YR？或者还有其他策略吗？
是的，这里至少有两种方法。
第一，正如王所建议的，是应用轮换。如果角度足够小，这相当于在与x进行比较后，通过y坐标打破关系，不需要其他数学运算。
第二个是调整G4G上的算法，使用线性时间划分算法来划分实例，并使用线性时间排序合并来征服实例。据推测，这并不是因为作者重视排序相对于大多数编程语言中前面提到的算法的简单性。
Tardos&Kleinberg建议用X中的位置(索引)来注释每个点。你可以在N次内做到这一点，或者，如果你真的，真的想，你可以做到"；免费"；在排序操作中。
有了这个注释，你可以进行O(1)分区，然后在O(2)中取Xl中最右边的点的位置pr，用它来确定Y中的点是在Yl(位置<=pr)还是Yr(位置>pr)。这不需要像哈希图那样的额外数据结构，但它确实需要在X和Y中使用相同的位置。
注：当多个点在x轴上具有相同的坐标时，Y的划分是唯一出现的问题，这对我来说并不明显。在我看来，跨分区的比较的线性证明是必要的，但我只看到了你只需要15个比较的证明，而不是更严格的7点版本的证明，所以我不能确定。