复形诱导生成CirclePacking的算法

1.问题描述

给定一个复形K和适当的“边界条件”，计算K对应的circle packing。

理论已证明这样的circle packing是存在且唯一的。

形如下图：

P为复形K诱导生成的CirclePacking

1.1符号定义与约束条件：

1)算法在欧式空间和双曲空间都成立

2）:表示点v及其一维邻域k个点，k个点逆时针排列

3），表示点v的度

4）我们强调不存在一价条件，也就是说，当顶点v和u不是邻居时，就不能保证它们的对应圆内部互不相交

5）中每个点映射为一个正实数，也就是CP中的圆半径（双曲几何中的半径可为无穷）

6）考虑下图：

Figure2

有定义：

余弦公式

其中x，y，z既表示点，也表示点映射的半径

7）

点邻域的实际角度和

8）每个内点的理想角度和应为2的正整数倍，记为，具体数值应该为已知条件

9）的边界处的半径给定，再加上复形，以及上的理想角度和，则存在与其对应的唯一的CirclePacking。

2.几何性质保证

2.1

2.2

引理1和2描述的是几个角度与圆半径的单调性关系
从几何直观很容易看出。

下面为一个关键的引理：

2.3 UNM

给定一个点，半径为，考虑其一维邻域，有：

也就是说，可以找到一个实数，来等效代替其邻域的其它不等的半径。

从而有以下引理，记为UNM：

描述了一种很奇妙的单调性，原论文中给出了证明。

3.算法雏形：

关于这个雏形，看起来有些像调和映照的思路，而其中“调和能量”将在后面给出。

4.细节：

4.1 能量函数

上式表示点处的能量，总能量即为所有点能量之和G（R）

4.2 UNM细节

Using the UNM requires two steps. First, given a value for v, determine so that .

Second, solve for a new value for v (call it u) so that

.

计算公式（欧拉平面与双区平面）在论文中已给出。

4.3局部线性收敛来加速算法

局部线性收敛满足以下等式：

可以简单推导出：

进而可用上式来加速收敛。

5.完整步骤

其中，表示UNM步骤，可以认为是能量，表示局部线性收敛的加速系数。

6.参考论文

Charles R. Collins, Kenneth Stephenson. A circle packing algorithm. Computational Geometry 25 (2003) 233–256