我正在从算法中学习测试，我发现了几天无法处理的问题。所以我写在这里寻求帮助。
对于平面上给定的两个不相交集：
G={(x_1^G, y_1^G), (x_2^G, y_2^G), ..., (x_n^G, y_n^G)}
D={(x_1^D, y_1^D), (x_2^D, y_2^D), ..., (x_n^D, y_n^D)}
Where for every 1 <= i, j <= n we have y_i^D < y_j^G, so G is above D.
找到一个有效的算法，
counts the distance between them
定义为：
d(G,D) = min{ d(a,b): a \in G and b\in D },
where d(a,b) = |x_a - x_b| + |y_a - y_b|
O(n^2) 是微不足道的，所以它不是答案。
我希望解决方案不会太难，因为它是从材料到测试前的审查。有人可以帮忙吗？
我认为这似乎是一些常见问题的特例。但如果是特殊情况，也许解决方案会更容易一些？
在 O(n log n) 时间内有几种不同的方法可以做到这一点。
一：计算G点的曼哈顿距离Voronoi图，并以此为基础构建点位置数据结构。这需要 O(n log n) 时间。对于每个 D 点，使用点位置数据结构找到最近的 G 点。每个 D 点需要 O(log n) 时间。取您刚刚找到的配对之间距离的最小值，这就是您的答案。
二：你可以用Fortune的算法来解决这个问题；只需为 D 和 G 点保留单独的二叉树。形容有点烦。
下一个想法计算无穷范数的最近对的距离，即 max(|x1-x2|, |y1-y2|)。您可以将问题倾斜 45 度（代入 u = xy，v = x+y）以将其转换为适当的形式。
三（二的变体）：按 y 坐标对所有点进行排序。保持 d，即目前看到的最近对之间的距离。我们将从上到下扫过一条线，维护两棵二叉搜索树，一个是 G 点，一个是 D 点。当一个点在扫描线上方 d 或更远时，我们将其从其二叉搜索树中删除。当扫描线第一次遇到一个点时，比如一个 D 点，我们 (1) 检查 G 二叉搜索树，看它是否有任何元素的 x 坐标在新点的 d 范围内，必要时更新 d， (2) 将新点插入到 D 的二叉搜索树中。每个点只导致恒定数量的二叉搜索树操作加上恒定数量的额外工作，因此扫描为 O(n log n)。不出所料，排序也是如此，因此我们的整体时间复杂度是符合要求的。
您也可以根据与三个类似的想法制定分而治之的策略。