随机增量构造

通用框架 ​

把 $n$ 个对象均匀随机排列，逐个插入并维护当前结构。这是随机算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。对最坏输入采用的内部随机顺序，不要求输入点来自随机分布。结构特征与尚未插入对象之间建立 conflict relation；插入对象 $x$ 时，只删除与 $x$ 冲突的旧特征、创建局部新特征，并更新相关冲突。

反向分析 ​

考察含 $i$ 个对象的最终结构，再把最后插入对象视为该集合中均匀随机的一个。若结构共有 $O(i)$ 个特征、每个特征由常数个对象定义，则最后对象参与的期望特征数为 $O(1)$；这等于正向第 $i$ 步的期望结构改变量。再加冲突更新即可求总期望成本。量词对固定输入、随机排列取期望。

梯形图例子 ​

增量插入互不相交线段构造平面梯形分解。新线段只穿过与它相交的一串现有梯形，替换成新梯形；history DAG 记录旧梯形如何被替换，使点定位查询沿历史走到当前叶，而不是每次扫描全部梯形。

退化与边界 ​

共线、相同端点或多对象同时定义特征会破坏“一般位置”计数，需符号扰动或明确 tie-breaking。只证明结构改变量小还不够，寻找冲突特征和更新 conflict graph 也要计时。若对手能根据已见随机顺序在线生成后续对象，固定输入的随机排列分析不再直接成立。

Conflict graph 与 history DAG ​

Conflict graph 将尚未插入对象连到它会破坏的当前特征。插入 $x$ 后，只需从 $x$ 的冲突邻居出发找到被删除特征，再测试其邻接对象与新特征；总成本分析要把这些测试计入，不能假设冲突集合免费获得。

History DAG 保留“旧特征被哪些新特征替代”的边。点定位从初始特征开始，只沿包含查询点的孩子前进；即使旧特征已不在当前结构，它仍提供搜索导航。删除全部旧节点会省空间，却失去查询路径。

冲突图的一次更新 ​

以平面梯形图为例，插入新线段时先沿当前点定位结构找到它穿过的梯形链。删除这些冲突梯形，按线段端点和上下边界切出新梯形，再把原来指向被删区域的查询 DAG 叶替换为局部判定节点；无关区域完全不动。

冲突图显式维护“未插入对象—当前特征”边时，处理步骤是：

1. 从新对象的冲突邻接表收集将被删除的特征；
2. 创建局部新特征并确定其边界；
3. 只扫描旧冲突邻居，把仍冲突的对象转接到新特征；
4. 删除失效特征及其冲突边。

反向分析把第 $i$ 步创建特征数等价为从随机大小 $i$ 结构中删除最后对象所破坏的特征数。若每个最终特征由常数个对象定义，成为“最后一个定义对象”的概率为 $O(1/i)$；退化输入若让一个特征有不确定定义集，就要先用符号扰动或显式 tie-breaking 固定组合类型。

参考资料

• Kenneth Clarkson, Peter Shor, Applications of Random Sampling in Computational Geometry II, Discrete & Computational Geometry, 1989.
• Mark de Berg et al., Computational Geometry, randomized incremental algorithms.