发现的最远点在一组从另一组 [英] Finding the farthest point in one set from another set
问题描述
我的目标是更有效的实现所提出的算法
My goal is a more efficient implementation of the algorithm posed in this question.
考虑两个点集合（在N-空间3空间为RGB色彩的示例情况，而对于<击> 1-空间 2空间中的溶液不同之处仅在距离计算）。你怎么找到的第一组是其最近的邻居在第二盘的最远点？
Consider two sets of points (in N-space. 3-space for the example case of RGB colorspace, while a solution for 1-space 2-space differs only in the distance calculation). How do you find the point in the first set that is the farthest from its nearest neighbor in the second set?
在1空间为例，给出了集合A：{2,4,6,8}和B：{1,3,5}，答案是 8，如8是3个单位距离5（其最近邻中的B），A的所有其他成员是仅有1个单位距离其最近的邻居中B.编辑：1-空间过于简化，作为排序相关距离的方式，所以不能在更高的维度
In a 1-space example, given the sets A:{2,4,6,8} and B:{1,3,5}, the answer would be 8, as 8 is 3 units away from 5 (its nearest neighbor in B) while all other members of A are just 1 unit away from their nearest neighbor in B. edit: 1-space is overly simplified, as sorting is related to distance in a way that it is not in higher dimensions.
在源问题的解决方案涉及在一组（所有的R，G，B的每一个点的蛮力比较，其中512> = R + G + B> = 256和R％4 = 0和G％4 = 0和B％4 = 0），以在另一组（colorTable）的每一个点。忽略，为了这个问题，第一组被编程的阐述，而不是迭代作为存储列表像第二盘。
The solution in the source question involves a brute force comparison of every point in one set (all R,G,B where 512>=R+G+B>=256 and R%4=0 and G%4=0 and B%4=0) to every point in the other set (colorTable). Ignore, for the sake of this question, that the first set is elaborated programmatically instead of iterated over as a stored list like the second set.
推荐答案
首先，你需要找到的每一个元素的近邻，在另一组。
First you need to find every element's nearest neighbor in the other set.
要做到这一点有效，你需要一个近邻算法。个人而言，我会实现一个 kd树只是因为我在我的算法类，它做到了在过去的相当简单。另一种可行的选择是 R树。
To do this efficiently you need a nearest neighbor algorithm. Personally I would implement a kd-tree just because I've done it in the past in my algorithm class and it was fairly straightforward. Another viable alternative is an R-tree.
执行一次在最小的集合中的每个元素。 （从最小添加一个元素，以较大的一个，并运行算法来找到它的近邻。）
Do this once for each element in the smallest set. (Add one element from the smallest to larger one and run the algorithm to find its nearest neighbor.)
从这个你应该能够得到近邻列表的每个元素。
From this you should be able to get a list of nearest neighbors for each element.
虽然找到最近邻居的对，将其保存在分类数据结构，它具有快速添加方法和快速GetMax的方法，诸如堆，排序欧氏距离。
While finding the pairs of nearest neighbors, keep them in a sorted data structure which has a fast addition method and a fast getMax method, such as a heap, sorted by Euclidean distance.
然后，一旦你完成简单的询问堆最大。
Then, once you're done simply ask the heap for the max.
这样做的运行时间分解如下：
The run time for this breaks down as follows:
N =大小的小套
M =大集大小
N = size of smaller set
M = size of the larger set
- N * O（登录M + 1）对所有kd树近邻检查。
- N * O（1），用于计算欧几里得距离将它添加到堆之前。
- N * O（日志N）的加入对入堆。
- O（1），以获得最终的答案：D
所以，最后整个算法是O（N * M）的。
So in the end the whole algorithm is O(N*log M).
如果你不关心每对可以通过只保留最大节省一点时间和空间的秩序迄今发现。
If you don't care about the order of each pair you can save a bit of time and space by only keeping the max found so far.
*免责声明：这你不会使用一个极其大量的维和你的元素遵循大多是随机分布的假设
*Disclaimer: This all assumes you won't be using an enormously high number of dimensions and that your elements follow a mostly random distribution.
这篇关于发现的最远点在一组从另一组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
