消除凸包之间的重叠

Question

在二维空间中，我们有两组点A和B以及它们各自的凸包C_A和C_B。假设C_A和C_B重叠。

什么是最佳算法，可以找到必须从A+B中删除的最小集合，使得结果凸包对不再重叠？

我相信这是一个已知的问题，但无法在任何地方找到参考资料。

- A. Roy

---

最小的（即，如果您将任何已删除的点添加回，则外壳会重叠）还是最小的（即尽可能保留多的点）？ - David Eisenstat

在这些术语中，我所指的是最小化-删除最少的点。 - A. Roy

Answer 1

我不知道最好的算法是什么，但我想出了一个O((n+m)^2)算法。

假设所有点都不同。否则，您需要修改算法。

如果两个凸包不相交，则存在一条完全分隔这些凸包的线。而且还有一条线，只有一个点位于该线上，可以将它们分开。因此，请按以下方式进行：

对于两个集合中的每个点P： 考虑通过P和所有其他点的直线。 按照所选点周围的角度对这些直线进行排序，并记住A和B上正面的点数。您将有大小为k < n+m的3个数组angles、countsA和countsB。 考虑这些角度之间的角度（在中间或不完全相同）。您将获得大小为k的数组angles2。 通过迭代数组angles，计算每组中位于通过具有角度angles2[i]的P的线的每侧的点数：nA1、nA2、nB1、nB2。 选择min(nA1+nB2, nA2+nB1)的最小值。 结束循环。 取找到的值的最小值。

没有必要计算angles2，您可以使用countsA和countsB的值并进行迭代更新。

- user20488960