随机增量构造 | Codeboy's Blog

形式陈述

通用框架

把 $n$ 个对象均匀随机排列，逐个插入并维护当前结构。这是随机算法对最坏输入采用的内部随机顺序，不要求输入点来自随机分布。结构特征与尚未插入对象之间建立 conflict relation；插入对象 $x$ 时，只删除与 $x$ 冲突的旧特征、创建局部新特征，并更新相关冲突。

反向分析

这一步需要明确结构如何由当前对象集合决定。一种常用的充分条件是：事先固定特征 $\sigma$ 的定义集 $D(\sigma)$ 与冲突集 $K(\sigma)$ ，满足 $|D(\sigma)|\le d$ ，其中 $d$ 为常数，且对每个对象子集 $R$ ，

\sigma\in F(R) \iff D(\sigma)\subseteq R\quad\text{且}\quad K(\sigma)\cap R=\varnothing.

组合退化的选择规则也事先固定； $F(R)$ 不随 $R$ 内部的插入顺序改变。对固定的大小为 $i$ 的前缀集合 $R_i$ ，最后插入对象 $x_i$ 均匀分布于其中。若 $\sigma$ 在第 $i$ 步新出现，则 $x_i\in D(\sigma)$ ：添加对象不能消除已有冲突，只能补齐一个缺失的定义对象。用指标变量与期望线性性得到

\mathbb E[\#\text{新特征}\mid R_i] \le\sum_{\sigma\in F(R_i)}\frac{|D(\sigma)|}{i} \le\frac{d\,|F(R_i)|}{i}.

若所有这样的集合都满足 $|F(R_i)|\le C i$ ，新特征期望数至多 $dC$ 。这里的集合不变性和出现条件不可用“每个特征涉及常数个对象”替代；依赖插入历史的结构需要另外的分析。只有当局部更新还能把每个被删旧特征常数次收费到新特征或 cavity 边界时，删除与创建的总改变量才同为 $O(1)$ 。再加冲突更新即可求总期望成本。量词对固定输入、随机排列取期望。

直觉

随机排列让第 $i$ 步的新对象等价于从当前 $i$ 个对象中均匀选择“最后一个”。如果每个最终特征只由常数个对象定义，最后对象成为其定义对象的概率便很小；正向创建对应逆向删除该对象时消失的特征。被删除旧特征还需由 locality 或 cavity 收费控制，而 conflict graph 负责让算法真正找到这些改动。

例子与边界

有序点间隙的反向计数

先看实线上的三个点 $R=\{1,4,9\}$ ，结构取相邻点之间的有界间隙。间隙的定义集是两个端点，冲突对象是严格位于端点之间的其他点，所以恰满足前述出现条件。最终有两份特征 $(1,4)$ 、 $(4,9)$ 。若最后插入的是 $1$ 或 $9$ ，各新建一个间隙；若最后插入 $4$ ，就把旧间隙 $(1,9)$ 换成两个新间隙。三种情况等概率，平均新建数为 $(1+2+1)/3=4/3$ ，也等于 $2|F(R)|/|R|$ 。这个计数仍没有支付“怎样找到被拆间隙”的搜索成本。

梯形图例子

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

退化与边界

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

推论与应用

Conflict graph 与 history DAG

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

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

LP-type 问题处理另一种压缩：保留优化值及未来违反关系，而不是保留全部几何特征。其极端元素是全部基的交，允许一份规范解有多种基；抽样恒等式计真正改变答案的删除，不把每条紧约束都当成唯一固定定义对象。

冲突图的一次更新

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

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

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

在前述固定定义集/冲突集条件下，反向删除最后对象所破坏的特征，恰对应正向新建的特征。其定义集大小为常数，最后对象落在其中的概率才为 $O(1/i)$ 。退化时应先固定一致的组合规则；若同一特征有多份定义证书，还要重新说明如何计数，不能直接套用唯一固定证书的式子。

参考资料

Kenneth L. Clarkson，A General Randomized Incremental Reconstruction Procedure，§3 的一般配置、定义对象与冲突条件。
Kenneth Clarkson, Peter Shor, Applications of Random Sampling in Computational Geometry II, Discrete & Computational Geometry, 1989.
Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, randomized incremental algorithms.

形式陈述 ​

通用框架 ​

反向分析 ​

有序点间隙的反向计数 ​

梯形图例子 ​

退化与边界 ​

Conflict graph 与 history DAG ​

冲突图的一次更新 ​

反向链接