从另一组中找到一组中的最远点

我的目标是更有效地实现此问题中提出的算法.

考虑两组点(在N空间中.3空间用于RGB颜色空间的示例情况,而1空间 2空间的解决方案仅在距离计算中不同).如何在第一组中找到距离其最近邻居最远的第二组中的点？

在1空间示例中,给定集合A:{2,4,6,8}和B:{1,3,5},答案为8,因为8距离5(最近邻居)3个单位在B)中,A的所有其他成员距离他们在B中的最近邻居只有1个单位.编辑:1空间被过度简化,因为排序与距离有关,而不是更高维度.

源问题中的解决方案涉及一组中每个点的强力比较(所有R,G,B,其中512> = R + G + B> = 256且R%4 = 0且G%4 = 0和B %4 = 0)到另一组中的每个点(colorTable).为了这个问题,忽略第一组以编程方式进行详细说明,而不是像第二组那样作为存储列表进行迭代.

首先,您需要在另一组中找到每个元素的最近邻居.

要有效地执行此操作,您需要最近邻居算法.就个人而言,我会实现一个kd-tree,因为我在算法类中已经完成了它并且它非常简单.另一种可行的替代方案是R树.

对最小集合中的每个元素执行一次此操作.(从最小到较大的一个元素添加一个元素并运行算法以找到它的最近邻居.)

从这里你应该能够获得每个元素的最近邻居列表.

在找到最近邻居对时,将它们保存在一个排序数据结构中,该结构具有快速加法方法和快速getMax方法,例如堆,按欧几里德距离排序.

然后,一旦完成,只需要求堆最大值.

运行时间分解如下:

N =较小集合的
大小M =较大集合的大小

所有kd树最近邻检查的N*O(log M + 1).

N*O(1)用于在将欧氏距离添加到堆之前计算欧几里德距离.

N*O(log N)用于将对添加到堆中.

O(1)得到最终答案:D

所以最后整个算法是O(N*log M).

如果你不关心每对的顺序,你可以节省一点时间和空间,只保留到目前为止的最大值.

*免责声明:这一切都假设您不会使用极高数量的维度,并且您的元素遵循大多数随机分布.