在曼哈顿距离中找到两个集合之间的距离 [英] Finding the distance between two sets in Manhattan distance
问题描述
我正在从算法中学习测试，发现了几天无法解决的问题。因此，我在这里写信寻求帮助。
对于给定的飞机上有两个不相交的集合：
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）}
对于每1< = i，j< = n，我们有y_i ^ D< y_j ^ G，所以G高于D。
找到一个有效的算法，使
计算它们之间的距离
定义为：
d（G ，D）= min {d（a，b）：a in G和bin in D}，
其中d（a，b）= | x_a-x_b | + | y_a-y_b |
O（n ^ 2）很小，所以这不是答案。
我希望解决方案不会太困难，因为它是从材料进行测试前进行审查的。有人可以帮忙吗？
我认为这似乎是某些常见问题的特例。但是，如果是特例，也许解决方案会更简单？
O（n log n）时间。
一个：计算曼哈顿距离 Voronoi图，并以此为基础建立点位置数据结构。这需要O（n log n）时间。对于每个D点，使用点位置数据结构查找最接近的G点。每个D点花费O（log n）时间。
两个：您可以调整《财富》算法；只需为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）。毫无疑问，排序也是如此，因此我们的总体时间复杂度是所希望的。
您也可以基于与三个类似的想法来制定分而治之的策略
I'm learning for the test from algorithms and I spotted problem that I cannot deal with for a few days. So I'm writing here for help.
For a given two disjoint sets on plane:
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.
Find an effective algorithm that
counts the distance between them
defined as:
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) is trivial, so it is not the answer.
I hope the solution isn't too hard since it is from materials to review before the test. Can anybody help?
I think it will appear that this is a special case of some common problem. But if it is a special case, maybe the solution can be easier?
There are a few different ways to do this in O(n log n) time.
One: Compute the manhattan distance Voronoi diagram of the G points and build a point location data structure based on that. This takes O(n log n) time. For each D point, find the closest G point using the point location data structure. This takes O(log n) time per D point. Take the min of the distances between the pairs you just found and that's your answer.
Two: You can adapt Fortune's algorithm to this problem; just keep separate binary trees for D and G points. Kind of annoying to describe.
The next idea computes the distance of the closest pair for the infinity-norm, which is max(|x1-x2|, |y1-y2|). You can tilt your problem 45 degrees (substituting u = x-y, v = x+y) to get it into the appropriate form.
Three (variant of two): Sort all of the points by y coordinate. Maintain d, the distance between the closest pair seen so far. We'll sweep a line from top to bottom, maintaining two binary search trees, one of G points and one of D points. When a point is d or farther above the sweep line, we remove it from its binary search tree. When a point is first encountered by the sweep line, say a D point, we (1) check the G binary search tree to see if it has any elements whose x-coordinate is within d of the new point's, updating d as necessary, and (2) insert the new point into D's binary search tree. Each point only causes a constant number of binary search tree operations plus a constant amount of additional work, so the sweep is O(n log n). The sort is too, unsurprisingly, so our overall time complexity is as desired.
You can probably make a divide-and-conquer strategy work too based on similar ideas to three.
这篇关于在曼哈顿距离中找到两个集合之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
