次线性但简单的动态凸包算法？
2026-02-18 02:31:59 策略智库
我假设总共有N个数据点，而复杂外壳由M个点定义。
维护凸包应该比首次构建凸包要容易得多（也更便宜）。
删除现有数据点
1/ If the data point in not one of the M points defining the convex hull then it won’t affect the hull so just remove it.
2/ If it is part of the convex hull then you need to adjust the hull – more on that below in point 4
添加新的数据点。
3/ If a data point is inside the complex hull then it will not affect the hull.
这里有一个简单的方法可以从我的头脑中测试这个。创建一个外壳内部的三角测量。使用M个点定义的复杂外壳可以被分解成M-2个三角形。然后测试该点是否位于其中一个三角形中。
4/ if a data point is outside the hull then it will become part of the hull. However, it is only affecting a local area of the hull and it is straightforward to find the new hull in a few steps. If you have already build the hull then it should be clear to you how to adjust a local part of it.
我不明白这些维护工作怎么可能是O(N)