第二十五章伞模型的计算几何基础

25.1 从Voronoi剖分到伞剖分

Voronoi剖分是计算几何中最基本的空间分割方式。给定平面上的一组点{pᵢ}，每个点pᵢ的Voronoi域V(pᵢ)定义为所有距pᵢ最近的点的集合。Voronoi剖分将平面分割成不重叠的凸多边形——每个点恰好属于一个Voronoi域。

这是一个完美的conforming结构：不重叠、无缝隙、每个空间点的归属唯一确定。Voronoi剖分的对偶——Delaunay三角化——给出了连接关系：两个Voronoi域相邻当且仅当对应的两个点被Delaunay边连接。

作者早期的研究工作就集中在Voronoi剖分和Delaunay三角化上。Centroidal Voronoi Tessellation（CVT）——将Voronoi域的重心与生成点对齐——是作者与杜强合作的核心成果之一。CVT产生的网格具有最优的几何性质——单元接近正多边形/多面体，分布均匀，质量高。

然而，从SDE的角度重新审视，CVT恰恰暴露了conforming范式的深层局限。

CVT的目标函数是能量泛函：E(X) = Σᵢ ∫_{V(pᵢ)} ρ(x) |x - pᵢ|² dx，其中X = {pᵢ}是生成点集，ρ是密度函数。最小化E得到CVT——每个生成点在其Voronoi域的质心处。这个优化是在所有可能的点集配置中寻找使每个"伞"（Voronoi域）最好地"覆盖"其区域的配置。

但关键限制是：Voronoi域不重叠。每个空间点只属于一个域。这意味着每个点只被一个"伞"覆盖——ω=1。所有的信息只通过Voronoi域的共享边交换——局域纠缠。

伞剖分是Voronoi剖分的SDE推广。不要求域不重叠——每个生成点pᵢ有一把伞Uᵢ = (pᵢ, rᵢ, φᵢ)，伞可以互相重叠。空间中的每个点可以同时属于多把伞。

定义伞剖分的能量泛函：

E_umbrella(X, R) = Σᵢ ∫ ρ(x) |x - pᵢ|² · φᵢ((x-pᵢ)/rᵢ) dx + λ · C(X, R)

第一项类似CVT能量但用核函数φᵢ加权——每把伞对空间的"负责"程度由核函数衰减控制，不是由Voronoi域的硬边界决定。第二项C(X, R)是重叠度约束或正则项——控制重叠的程度。

当φᵢ = 1_{V(pᵢ)}（Voronoi域的指示函数）时，伞剖分退化为Voronoi剖分。当φᵢ是高斯函数或其他光滑核函数时，伞剖分允许重叠——而且重叠量由rᵢ控制。

最小化E_umbrella得到centroidal umbrella tessellation——每把伞的中心在其加权覆盖区域的质心处，伞的半径和形状适应局部物理纠缠的需求。

与CVT的关键区别：CVT的优化变量只有点的位置X。伞剖分的优化变量包括位置X和伞参数R = {rᵢ}。伞的大小本身是优化的结果——在纠缠强的区域伞自动变大（覆盖更广以捕捉非局域纠缠），在纠缠弱的区域伞自动变小（局域覆盖就够了）。

这就是从conforming到SDE的几何基础的转变：从Voronoi的硬边界不重叠域，到伞的软边界重叠域。从固定的空间分割，到自适应的纠缠覆盖。

25.2 Delaunay对偶的推广

Voronoi剖分的对偶是Delaunay三角化——它给出了生成点之间的连接关系。在SDE框架中，这个对偶需要推广。

传统的Delaunay连接是二值的：两个点要么连接（Delaunay边存在）要么不连接。连接关系只取决于点的几何位置——两个点的Voronoi域共享边界时才连接。

伞连接是连续的：两个伞的纠缠强度E(i,j) = ∫φᵢ·φⱼ dx可以是0到正无穷之间的任何值。纠缠强度取决于伞的重叠程度——重叠多则纠缠强，重叠少则纠缠弱，不重叠则不纠缠。

传统的邻接图是无权图（边存在或不存在）。伞的纠缠图是加权图（边的权重是纠缠强度）。而且伞的纠缠图一般不是稀疏的——大伞可以跟远处的伞重叠，产生长程连接。

这个加权纠缠图取代了传统的Delaunay三角化作为计算的基础数据结构。Assembly不是在Delaunay边上做局域组装，而是在纠缠图的所有边（包括长程边）上做加权组装。Solver不是利用稀疏矩阵的结构，而是利用纠缠图的衰减结构——远程纠缠弱，可以被快速多极展开或H-matrix近似。

25.3 多层伞剖分

在Voronoi剖分中只有一层——一组点产生一组不重叠的域。在SDE框架中需要多层——每层对应一个尺度的纠缠。

定义多层伞剖分：𝓤 = {𝓤₁, 𝓤₂, ..., 𝓤_L}，其中𝓤_l = {Uᵢ^(l) = (xᵢ^(l), rᵢ^(l), φᵢ^(l))}是第l层的伞场。不同层的伞半径不同：r^(1) < r^(2) < ... < r^(L)——第一层是小伞（细尺度纠缠），最后一层是大伞（粗尺度纠缠）。

各层之间在空间上完全重叠——同一个区域同时被小伞、中伞、大伞覆盖。跨层的纠缠强度定义为：

E_cross(i^(l), j^(m)) = ∫ Φᵢ^(l)(x) · Φⱼ^(m)(x) dx, l ≠ m

这量化了不同尺度伞之间的纠缠——一个小伞跟覆盖它的大伞之间有多强的跨尺度耦合。

多层伞剖分的能量泛函包含层内能量和层间能量：

E_multi = Σ_l E_l(𝓤_l) + Σ_{l<m} μ_{lm} · E_cross(𝓤_l, 𝓤_m)

第一项驱动每层内的伞分布优化，第二项驱动层间的协调——太多跨层纠缠意味着尺度没有被正确分离，太少跨层纠缠意味着尺度之间的物理耦合被忽略。

最优的多层伞剖分自动确定每层的伞数量、位置、大小，以及层间的耦合强度——全部从物理纠缠场中涌现，不需要人为预设。

25.6 案例：Voronoi-Delaunay对偶的伞模型重述【A类核心证据】

Voronoi剖分和Delaunay三角化是计算几何中最基本的对偶结构。从伞模型角度，它们获得了全新的理解。

给定平面上N个点（种子点）。每个种子点x_i的Voronoi区域V_i是所有离x_i最近的点的集合。Delaunay三角化是Voronoi图的对偶——如果两个Voronoi区域共享一条边，则连接对应的两个种子点。

伞模型的重述： 每个种子点x_i就是一个伞的中心。Voronoi区域V_i就是这个伞的覆盖范围——在r→∞的退化极限下，伞的覆盖范围退化为"最近邻区域"。Voronoi边就是两个伞的覆盖范围的边界——两个伞在这里"势均力敌"。

关键认识：标准Voronoi/Delaunay假设了ω=1——每个空间点只属于一个Voronoi区域。这就是conforming的局域纠缠假设。如果允许ω>1——一个空间点可以同时属于多个"伞"——就得到加权Voronoi图或power diagram。每个种子点不仅有位置还有"权重"（伞的强度），权重大的伞可以覆盖到更远的地方，使得边界向权重小的伞偏移。

Power diagram已经在计算几何中有广泛应用。但SDE的视角更深——power diagram只是ω=2的特例（每个点最多属于两个伞的竞争区域）。如果允许ω→∞——一个点同时被所有伞覆盖，权重决定影响力——就回到了非局域场论。Voronoi→power diagram→非局域场，是伞参数ω从1到∞的连续撑开。

作者的Voronoi mesh generation工作（1990年代-2000年代）可以在这个谱系中精确定位：它是ω=1（标准Voronoi）到ω略大于1（带质量的Voronoi，weighted centroidal Voronoi tessellation[23]）的小步扩展。SDE数学要求的是ω>>1的大步扩展——进入真正的非局域纠缠网络。