用于比较 2 个不同数组中的点的最近对算法

Question

我想将一个数组中的点与另一个数组中的点进行比较并找到最接近的一对。到目前为止，我遇到的都是单个数组。我不想比较同一数组中的点。暴力算法可以工作，但速度太慢。是否有使用分而治之方法的算法或实现？

编辑1：点被定义为地球表面上的一对（纬度，经度）。

Answer 1

您可以为第一个点数组构建一个 kd 树，然后使用该树为第二个数组的每个点找到距离第一个数组最近的点。它的平均复杂度为 O(n log n)（n 是两个数组中最大的一个数组的大小）。要使用 kd-tree，您可以将初始坐标转换为 3D 空间坐标。