消除凸包之间的重叠

Question

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

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

我确信这是一个已知问题，但在任何地方都找不到参考。

Answer 1

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

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

如果两个凸包不相交，则存在一条线将这些凸包完全分开。还有一条线将它们分开，线上只有一个点。因此，请按以下步骤操作：

1. 对于两个集合中的每个点 P：
2. 考虑穿过 P 和所有其他点的线。
3. 按围绕所选点的角度对这些线进行排序，并记住位于线正侧的 A 和 B 点的数量。您将有 3 个数组angles，大小countsA为countsBk < n+m。
4. 考虑这些角度之间的角度（在中间或不完全在中间）。你将得到一个angles2大小为 k 的数组。
5. 迭代数组，angles计算位于经过 P 且角度为angles2[i]: nA1, nA2, nB1,的线每一侧的每组点的数量nB2。
6. 选择 的最小值min(nA1+nB2, nA2+nB1)。
7. 结束为。
8. 取找到的值中的最小值。

无需计算，您可以使用和angles2的值并迭代更新。countsAcountsB