移除凸包间重叠：求解最小点集移除的最优算法

给定二维点集A、B，它们的凸包C_A、C_B存在重叠，目标是从A∪B中移除最少的点，使得剩余点集的凸包不再有交集。以下是针对该问题的最优解法思路：

核心观察 #

只有凸包顶点会影响凸包的形状和范围，移除内部点不会改变凸包结构。因此最小移除集合必然只包含凸包顶点，无需考虑内部点。

算法步骤 #

1. 定位关键顶点 #

• 遍历C_A的所有顶点，找出落在C_B内部或边界上的点，记为集合S_A；同理找出C_B中落在C_A内部或边界上的点，记为集合S_B。
• 若两个凸包的边存在交点，记录这些交点对应的凸包顶点（这些顶点是维持交叠区域的关键支撑点）。

2. 分情况处理重叠类型 #

凸包重叠分为两种典型情况，对应不同的最优移除策略：

情况1：一个凸包完全包含另一个（如C_A ⊇ C_B）

此时有两种可选方案：

• 方案一：移除C_A中足够多的顶点，使得C_A收缩后的凸包C_A'无法再包含C_B的任何点。具体是移除C_A中那些构成“包围”C_B的边界顶点，直到C_A'的范围完全不覆盖C_B。
• 方案二：移除C_B中所有位于C_A内部的顶点，使得C_B收缩后的凸包C_B'完全处于C_A外部。
  取两种方案中移除点数更少的那个作为最优解。

情况2：两个凸包相交（互相部分覆盖，无完全包含关系）

这种情况下，交叠区域由C_A和C_B的部分边界共同构成。我们可以将问题转化为二分图最小顶点覆盖问题：

• 构建二分图：左节点集为S_A，右节点集为S_B。若C_A的顶点a和C_B的顶点b共同构成了交叠区域的一条支撑边（即这两个顶点所在的凸包边参与形成交叠区域），则在a和b之间连一条边。
• 根据Konig定理，二分图的最小顶点覆盖等于其最大匹配。通过求解最大匹配，即可得到最少需要移除的顶点数——覆盖所有边的最小顶点集合，就是需要移除的点，移除后两个凸包的边界将不再相交，凸包自然分离。

3. 验证结果 #

移除候选点后，重新计算剩余点集的凸包，验证二者是否确实无交集，确保没有遗漏交叠的情况。

复杂度分析 #

• 关键顶点定位：O(m log n + n log m)，其中m、n分别是C_A、C_B的顶点数（判断点是否在凸包内的时间为O(log k)，k为目标凸包的顶点数）。
• 二分图最小顶点覆盖：O(√(m+n) * E)，E为二分图的边数，通常远小于m*n，效率较高。

内容的提问来源于stack exchange，提问作者A. Roy