Arora Algorithm 2 Random Partition

发表于 更新于 分类于 ， 阅读次数：

Arora算法, 随机分割.

Random Partition

定义边界框 (bounding box)为边长为\(2\)的幂次的包住所有实例顶点的最小正方形, 设其边长为\(l\). 实例确定后便放置并固定该正方形.

定义封闭框 (enclosing box)为边长为\(L=2l\)的正方形, 其位置由参数\(a,b\)以及bounding box三者共同确定, 其中\(a,b\)为从\(\{1,2,\ldots,l\}\)中随机抽取的正整数.

bounding box和enclosing box的一个图示如下.

递归地四分enclosing box, 直至正方形地边长为\(1\),易知分割共可进行\(\log L\)次. 给参与第\(i\)次划分的水平或垂直线分配等级 (level) \(i-1\). 给正方形分配level如下: 设enclosing box的level为\(0\), 接着按正方形的大小降序依次分配等级. 一个\(L=8\)的例子如下图所示.

下简述一个随机分割的重要性质. 对任意与bounding box相交的垂直线, 它的level是随\(a\)的选择而变化的. 考虑其level为\(i\)的概率 (\(i=0,1,\ldots,\log L-1\)). 观察到此时间发生时, \(a\)的选取可能性共有\(2^i\)种, 因此 \[ \operatorname{Pr}_{a}[\text {线位于}\textit{level } i]=\frac{2^{i}}{l}=\frac{2^{i+1}}{L}. \]