我正在从算法中学习考试，我发现了几天无法处理的问题。所以我在这里写信寻求帮助。
对于给定的平面上两个不相交的集合:
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.
找到一个有效的算法
计算它们之间的距离
定义为:
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) 是微不足道的，所以它不是答案。
我希望解决方案不会太难，因为它是从 Material 到测试前的审查。有人可以帮忙吗？
我认为这似乎是一些常见问题的特例。但如果是特殊情况，也许解决方案会更简单？
最佳答案
有几种不同的方法可以在 O(n log n) 时间内完成此操作。
一:计算曼哈顿距离Voronoi diagram的 G 点，并以此为基础构建点位置数据结构。这需要 O(n log n) 时间。对于每个 D 点，使用点位置数据结构找到最近的 G 点。每个 D 点需要 O(log n) 时间。取你刚刚找到的对之间距离的最小值，这就是你的答案。
二:可以适配Fortune's algorithm对于这个问题；只需为 D 和 G 点保留单独的二叉树。有点烦人的描述。
下一个想法是计算无穷范数中最近对的距离，即 max(|x1-x2|, |y1-y2|)。您可以将您的问题倾斜 45 度(替换为 u = x-y，v = x+y)以使其成为适当的形式。
三(二的变体):按 y 坐标对所有点进行排序。维护 d，即到目前为止看到的最近对之间的距离。我们将从上到下扫描一条线，维护两个二叉搜索树，一个是 G 点，一个是 D 点。当一个点在扫描线上方 d 或更远时，我们将其从二叉搜索树中删除。当扫描线第一次遇到一个点时，比如 D 点，我们 (1) 检查 G 二叉搜索树，看它是否有任何元素的 x 坐标在新点的 d 范围内，必要时更新 d， (2) 将新点插入到 D 的二叉搜索树中。每个点只引起恒定数量的二叉搜索树操作加上恒定数量的额外工作，所以扫描是 O(n log n)。不出所料，排序也是如此，因此我们的整体时间复杂度符合要求。
您也可以根据与三个类似的想法使分而治之的策略发挥作用。
关于algorithm - 找到曼哈顿距离中两组之间的距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13778044/