区分两组不同点的算法？

Question

我被给了两组要点：我们称他们为组I和组II。他们都是在飞机上绘制的。我如何将第一组与第二组区分开来，当每个组包含数千个点时，只有计算机知道哪一个是哪一个？

找到一种方法来区分两组点之后，我会给出一组来自第I组和第II组的点，但我不知道哪一点在哪个组中。

Answer 1

虽然目前还不清楚这种方法是否产生了一种在实践中可行的解决方案，但可能的解决方案如下。

计算两个点集的边界框并移动边界框以匹配;之后，通过使组I成为左侧分区和组II右侧分区来模拟bipartite matchig问题。节点之间的边缘权重为Euclidean distance。如果最小权重的匹配具有权重零，则组I和组II是相等的（因为可以匹配点）;如果权重大于零，则组I和组II是不同的。使用Hungarian algorithm可以在多项式时间内解决二分匹配问题。