最近在逛Siggraph 2026的文章时淘到了一篇将持续同调与图形学结合得极为巧妙的文章Rong L, Ju T. Persistence-guided Prescribed Topological Simplification[J]. ACM Transactions on Graphics (TOG), 2026, 45(4): 1-16. 与对13年前的一篇文章Dey T K, Fan F, Wang Y. An efficient computation of handle and tunnel loops via Reeb graphs[J]. ACM Transactions on Graphics (TOG), 2013, 32(4): 1-10.的感觉类似, 可以说都让我爱不释手. 前几年本来是有类似的想法, 以持续同调的观点解释减面的过程, 但奈何对持续同调的理解不够深刻, 当时也没继续落地. 此次看到这篇文章, 自然让我赶紧拜读了起来. 本来以为在AI的辅助下, 研读的过程会十分顺利, 结果没想到自己太菜, 依旧是读得磕磕绊绊的. 所幸断断续续耗时一个月, 总算是啃下来了, 顺带在UE中也实现了一版效果.
参考材料
1. Linxuan Rong and Tao Ju. [Persistence-guided Prescribed Topological Simplification](https://doi.org/10.1145/3811384). ACM Transactions on Graphics, 45(4), Article 165, 2026.
这篇论文允许用户指定形状中要保留的连通分支, 贯穿通道和空腔数量. 作者按持久度选择保留的特征, 从骨架构造切割与填充候选, 再用加权最小割选择一批无冲突操作, 减少几何改动. 阅读时, 我反复核对的是候选能否只消除预期特征, 以及最小割和表面提取各自保证了什么. 接下来的内容配合原论文”食用” 效果更佳(●ˇ∀ˇ●)
1. 目标数量与修复位置
论文输入一个形状$S$和目标Betti数$b_k \le \beta_k(S)$, 希望输出$S’$满足$\beta_k(S’) = b_k$, 同时减少几何改动. 三维中的$\beta_0$表示连通分支数, $\beta_1$表示贯穿通道数, $\beta_2$表示封闭空腔数. 用户可以保留若干通道和空腔, 不必把目标设成只有一个分支, 没有通道和空腔的平凡拓扑.
$\\$ Betti数只规定数量. 减少一个通道, 既可以切开实体的一部分, 也可以填住通道. 两种操作的几何代价不同, 多个操作之间还可能冲突. 算法需要从这些修改方式中选出能一起执行的一批.
$\\$ 作者保留每类特征中持久度最高的指定数量. 持久度提供排序依据, 却无法区分重要结构与尺度较大的重建错误. 用户仍需根据应用确定目标数量和代价度量.
$\\$ 论文只简化当前形状对应的一个过滤前缀. 在其它时刻存在, 当前形状中不存在的特征, 可以保留在过滤里. 后面的迁移证明也只要求保护当前形状中应保留的特征.
2. 整体流程与中间产物
论文第4节把方法分成输入转换, 过滤简化和表面提取三步. 其中过滤简化是一个循环: 计算持续配对与代表链, 构造形状和背景的骨架, 生成候选, 用图割选择候选, 再迁移选中的胞.
算法用骨架寻找可以删除的出生胞或可以填入的死亡胞, 再确定它们在原形状中对应的修改范围. 作者也在实验中画出骨架, 帮助观察通道和空腔. 骨架在这里是中间产物, 最终输出为简化后的形状及其表面网格.
$\\$ 每轮图割在已有候选中找到数量最多, 总代价最低的无冲突集合, 后续迭代再处理剩余次要特征. 这个最优性限定在当前候选集合内. 作者没有证明整个过程能找到几何修改的全局最优解, 也没有保证任意输入都能达到目标Betti数.
3. 从网格或隐式场建立过滤
过滤由环境胞复形$\mathbb X$, 胞的全序$\pi$和时间函数$f$组成. $\pi$要求面先于上胞, 因而每个前缀都是胞复形; $f$沿$\pi$不减. 同一时间可以包含多个胞, 但排序时仍要满足面关系.
$\\$ 下文沿用论文的环境与系数约定: $\mathbb X$具有平凡拓扑, 任意胞的时间都不为零, 链的加法按模2计算. 对偶关系也采用论文第3.3节的背景构造, 不推广到任意胞复形. 目标为非空形状时, 连通分支数至少为1.
$\\$ 对网格上的隐式场$g$, 论文第6.1节在顶点处取$f(v) = g(v)$, 其它胞的时间取其顶点值的最大值:
$$
f(\sigma) = \max_{v\text{为}\sigma\text{的顶点}}g(v).
$$这个定义保证面的时间不大于上胞的时间. 将胞按时间排序, 并在并列时让面先进入, 就得到合法过滤. 形状取负时间子复形:
$$
\mathbb X_f = \{\sigma \in \mathbb X \mid f(\sigma) < 0\}.
$$因此一个胞只有在全部顶点都为负时才进入初始形状. 四面体网格中的这种负子复形与相应分片线性场的负区域具有对应的拓扑; 立方网格则采用负顶点的6连通约定. 讨论三维实体的Betti数时, 不能把负区域与它的二维零等值边界混为一谈.
$\\$ 三角网格输入可以先转换为有符号距离体, 也可以先构造贴合表面的四面体网格, 再计算顶点的有符号距离. 前一种方式可能丢失细小几何; 后一种方式更依赖四面体剖分的质量与规模. 作者还用小偏移避开恰好为零的顶点值, 以便用严格正负号区分形状与背景.
$\\$ 迁移后, 高维胞的时间可能不再等于其顶点时间的最大值. 表面提取时需要处理这个差异, 不能只读取原顶点值.
4. 用活跃配对选择要保留的特征
持续配对$\{b,d\}$记录一个同调类的出生与死亡. 对$k$维特征, 出生胞$b$为$k$维, 死亡胞$d$为$k + 1$维; 持久度为$f(d) – f(b)$. 对始终不死亡的类, 采用无限死亡时间的约定.
$\\$ 当前形状位于零时刻, 所以只有满足$f(b) < 0 < f(d)$的配对代表其中尚存的特征. 论文称这些配对为活跃配对. 每一维中, 活跃配对按持久度排序, 前$b_k$个为主要配对(Major), 剩余待消除的为次要配对(Minor). 主要与次要集合的分界若存在持久度并列, 还需核对并列规则与迁移证明是否相容; 不能仅凭任意固定排序就断言主要配对的身份保持不变.
$\\$ 对次要配对, 可以把出生胞从负时间移到正时间, 或把死亡胞从正时间移到负时间. 若迁移后的配对两端位于零时刻同侧, 它就不再代表当前形状中的特征. 这些胞仍在环境复形里, 也可能继续构成非活跃的持续配对.
$\\$ 单独改一个胞的符号未必合法. 删除面却保留它的上胞, 或添加一个缺少面的胞, 都会破坏胞复形条件. 把相关胞一起迁移也可能误改其它特征, 因此构造候选时还要控制其拓扑效果.
5. 保护代表循环的骨架化
胞$\sigma$在当前复形中没有上胞时, 称为孤立胞. 这里的孤立指面关系: 一个与邻居共享边, 但没有三维上胞的三角形, 仍是孤立的二维胞. 若它的一张面$\phi$只有$\sigma$这个上胞, 二者构成简单对$\{\phi,\sigma\}$. 同时删除它们是一次保持同伦类型的初等塌缩.
作者反复删除简单对来计算形状骨架$K$, 但额外禁止删除任何活跃配对生成元上的胞. 生成元(Generator) 是该同调类的代表循环, 包含其出生胞$b$. 保护生成元就保证活跃出生胞留在骨架中, 同时让删除的简单对满足附录A.5的条件.
$\\$ 次要配对的生成元也要保留, 因为后面需要对尚未选中的活跃配对继续使用原代表链. 简单对塌缩本身保持同伦类型, 即使不保护生成元也不会改变Betti数; 但它可能移除原代表链中的胞. 保护生成元提供的是A.5所需的代表链避让条件, 比单纯保持同伦更强.
$\\$ 骨架可能包含边和面, 分别支撑通道和空腔等特征. 保护代表循环的限制也可能阻止进一步塌缩. 因此, 这里得到的是用于构造候选的骨架, 不保证唯一或全局最小.
6. 生成集合如何定义切割与填充?
设$K$由$X$按顺序删除一批简单对得到, 出生胞$b$在$K$中孤立. 生成集合$G_{X,K}(b)$取自已删除的胞与$b$, 是其中包含$b$并对$X$中的上胞封闭的最小集合. 直观上, 从骨架里要删的$b$出发, 把原形状中依赖它的胞一起纳入删除范围.
$\\$ 删除生成集合后, $X \setminus G_{X,K}(b)$仍是胞复形, 并与$K \setminus \{b\}$同伦等价. 作者据此把$G_{\mathbb X_f,K}(b)$定义为$b$的切割候选. 生成集合本身通常不向下封闭, 无需构成胞复形; 它表示操作范围, 与表示循环的生成元不同.
$\\$ 填充在背景侧用同一套构造. 普通补集$\bar X = \mathbb X \setminus X$可能缺少某些胞的面, 因而不一定是胞复形. 对偶反转面与上胞关系, 使对偶补集成为背景胞复形:
$$
\widetilde X = \widehat{\bar X} = \widehat{\mathbb X} \setminus \widehat X.
$$形状过滤$\{\mathbb X,\pi,f\}$对应背景过滤$\{\widehat{\mathbb X},-\pi,-f\}$, 其中$-\pi$表示逆序. 按论文使用的持续同调与持续相对上同调对偶, 有限配对满足$\{b,d\} \leftrightarrow \{\widehat d,\widehat b\}$. 若环境复形的维数为$n$, $k$维形状特征对应$n – k – 1$维背景特征.
$\\$ 作者在背景骨架化时保护余生成元(Co-generator), 即背景侧的代表循环. 对形状配对$\{b,d\}$, 它包含$\widehat d$. 若$\widehat d$在背景骨架中孤立, 就构造其生成集合并转回原复形, 得到$d$的填充候选. 填充原形状, 等价于从对偶背景删除这组胞.
$\\$ 出生胞或对偶死亡胞若在相应骨架中不孤立, 就无法按上述规则生成切割或填充. 例如, 为了保留其它活跃特征的代表循环, 算法可能必须保留目标的上胞. 这个配对在本轮便可能缺少一种, 甚至两种候选.
7. 合法迁移与命题5.1
设$C$为选中切割的胞并集, $F$为选中填充的胞并集. 切割取自负时间胞, 填充取自正时间胞, 二者原本就没有共同胞. 论文所说的”互不相交” 还要求: $C$中任何胞都不能有上胞属于$F$. 这是面关系约束, 比集合交集为空更强.
$\\$ 令$N$, $P$分别为原过滤中的负时间与正时间序列. 迁移按以下顺序稳定重排, 各组内部保留原相对顺序:
$$
\pi’ = (N \setminus C)\;|\;F\;|\;C\;|\;(P \setminus F).
$$给$F$分配靠近零的负时间, 给$C$分配靠近零的正时间, 并保持时间沿$\pi’$不减. 实现可以直接构造这个结果, 无需模拟附录证明里的每次相邻交换.
$\\$ 切割包含目标的负时间上胞, 填充包含目标缺少的正时间面, 而互不相交条件排除了删掉面却添加其上胞的冲突. 这些闭包与面关系条件保证了重排的合法性, 不能省略后只做批量符号翻转.
$\\$ 命题5.1证明: 选中$m$个符合条件的次要配对候选, 迁移后保持合法过滤与原有主要配对, 并恰好减少$m$个次要活跃配对. 后面的优化用候选数量衡量消除的特征数, 依据就在这里.
8. 把候选选择变成二分图问题
把每个切割候选表示为$V_c$中的一个顶点, 每个填充候选表示为$V_f$中的一个顶点. 若一对切割与填充不满足互不相交条件, 就在它们之间连边. 同侧候选之间不连边, 得到二分冲突图$G = (V_c \cup V_f,E_G)$.
$\\$ 独立集对应一组无冲突候选. 根据命题5.1, 要在本轮消除最多次要特征, 就应选最大独立集. 文中的MIS指Maximum Independent Set, 不是仅仅无法再加入顶点的极大独立集. 数量相同的最大独立集可能有多个, 下一步再用几何代价区分它们.
$\\$ 作者先构造单位容量网络$H$: 添加源点$s$和汇点$t$, 令$s \to c$与$f \to t$容量为1, 冲突弧$c \to f$容量为$\infty$. 对有限容量割$(S,T)$, 取$s \in S$, $t \in T$, 定义覆盖$U$与独立集$I$:
$$
U = (V_c \cap T) \cup (V_f \cap S),\qquad
I = (V_c \cap S) \cup (V_f \cap T).
$$若某条冲突边的两端都不在$U$, 就有$c \in S,f \in T$, 割中将包含无穷容量弧. 因此$U$覆盖所有冲突边, 且有限割边与$U$的顶点一一对应, 割容量为$|U|$. 反过来, 每个顶点覆盖也能构造同容量的割. 最小割于是对应最小顶点覆盖, 其补集就是最大独立集.
$\\$ 反向构造不能省略, 否则只能说明割给出了某个独立集, 还不能证明它最大. 给定任意顶点覆盖$U$, 将$V_c \setminus U$与$V_f \cap U$放到源点侧, 将其余候选放到汇点侧, 再分别加入$s$, $t$. 若存在从源点侧到汇点侧的冲突弧$c \to f$, 则$c$, $f$均不属于$U$, 与覆盖条件矛盾. 所以割只包含与$U$对应的单位容量边, 容量恰为$|U|$. 现在假设最小割给出的独立集$I$不是最大的, 则更大独立集的补集就是更小覆盖, 由这一构造会得到更小的割, 产生矛盾.
$\\$ 原图中的紫色曲线只表示分区. 选点时取左侧候选中位于源点侧的点, 加上右侧候选中位于汇点侧的点. 按原图从上到下编号, 独立集为$\{c_3, f_1, f_2, f_3\}$, 覆盖为$\{c_1, c_2, f_4\}$. 另外, 有向割只计算$S \to T$的弧, 不能仅凭线条穿过分界就把它算入容量.
9. 在数量最多的方案中最小化代价
论文允许用户为每个候选指定几何代价$w(v)$. 第7节默认对切割取$|f(b)|$, 对填充取$|f(d)|$, 偏好时间函数意义上更靠近形状的操作. 这个代价与持久度$f(d) – f(b)$不同: 持久度用于决定特征是否应保留, $w(v)$用于比较消除次要特征的操作.
$\\$ 作者把$H$中有限边的容量从1改为$W – w(v)$, 其中$W$为全部候选的总代价, 得到$H^*$. 节点, 边, 方向与冲突弧容量保持不变. 对有限割$E$, 记覆盖为$U_E$, 独立集为$I_E$, 有:
$$
\operatorname{cap}_{H^*}(E)
= |U_E|W – w(U_E)
= (|U_E| – 1)W + w(I_E),
$$其中, $w(A)$为集合$A$中顶点代价之和. 覆盖大小相同时, 第一项为常数, 最小化割容量就等于最小化所选独立集的代价. 直接把有限容量设成$w(v)$, 优化的将是覆盖的代价, 不是保留的独立集.
$\\$ 对正代价且至少有一条冲突边的图, 命题5.2的证明先说明$H^*$的最小割也是$H$的最小割, 保证所选数量最大. 冲突边使顶点覆盖非空; 若另一个覆盖少一个顶点, 容量中少掉的$W$足以严格压过代价项的变化. 然后在$H$的最小割之间比较, 因为覆盖大小相同, 就可以消去常数项, 得到总代价最小.
$\\$ 这里严格小于零的来源值得单独写出. 设$U^*$是$H^*$最小割的覆盖, 反设另有覆盖$U$满足$|U| \le |U^*| – 1$, 并用上一节的构造得到割$E$. 记$U^*$对应的割为$E^*$, 则:
$$
\operatorname{cap}_{H^*}(E) – \operatorname{cap}_{H^*}(E^*)
\le -W – w(U) + w(U^*)
\le -w(U) < 0.
$$其中第二个不等号使用$w(U^*) \le W$, 最后一个严格不等号使用$U$非空且顶点代价均为正. 这才与$E^*$最小矛盾. 得到覆盖数量最少后, 后续比较只在相同覆盖数量的割之间进行, 并不需要反过来证明$H$的每个最小割都是$H^*$的最小割.
$\\$ 无冲突边时直接选择全部候选即可. 原文附录B关于覆盖非空的论证没有覆盖这个退化情况: 若图只有一个候选$v$, 就有$W - w(v) = 0$, 某个零容量最小割也可能不选$v$. 因此实现应单独处理无冲突图, 或采用下述更大的容量常数; 不能把原文公式理解为对任意退化图都无需处理.
$\\$ 我曾疑惑第二步是否还需要$H$. 它仍用于界定"数量同样最多" 的比较范围, 但比较容量时使用$H^*$. 实现只需求解$H^*$, 无需先求解$H$. 逆命题也不成立: $H$的某个最小割只保证数量最多, 未必满足第二级代价目标.
$\\$ $W – w(v)$可以称为补权容量. 它在建图时确定, 与最大流运行中的残余容量不同. 后者取决于当前流量, 正向弧剩余量为$c(u,v) – x(u,v)$, 反向残余弧用于撤回流量. 对非负代价, 可用$M > W$构造$M – w(v)$, 严格保证数量优先, 同时处理零代价与上述退化情况. 这是实现扩展, 不适用于未经重新推导的负代价输入.
10. 为什么一轮图割之后还要迭代?
图割能找到给定候选中的最优集合, 但有些次要配对可能没有候选, 现有候选也可能相互冲突. 作者观察到, 不孤立的出生胞或对偶死亡胞常位于其它活跃配对的代表循环上. 为保护这些循环, 骨架化不能把目标附近的胞继续塌缩掉.
$\\$ 消除一批次要配对后, 下一轮需要保护的代表循环减少. 作者重新计算持续同调和两侧骨架, 尝试生成上一轮缺失的切割或填充. 在旧冲突图上重复求最小割, 无法提供这些新候选.
$\\$ 算法1在候选为空时停止. 候选非空时, 至少能选择一个顶点; 命题5.1保证次要配对数下降, 所以循环会终止. 若终止时已没有次要配对, 就达到了目标Betti数. 若仍有次要配对但无法生成候选, 算法也会停止, 这是理论保证的边界.
$\\$ 若每个次要配对都有切割和填充候选, 选择全部切割或全部填充就能消除全部次要特征. 论文用这一充分条件说明候选缺失的影响: 图割即使求出了本轮最优解, 也无法选择尚未生成的操作.
11. 修改胞复形之后, 如何提取表面?
简化后的负胞复形可能包含面和边等低维结构, 它的边界不一定直接给出所需的流形三角网格. 第6.2节因此单独处理输出: 在保留负子复形拓扑的前提下, 把修改后的胞时间转成可供等值面算法读取的信息.
$\\$ 直接用顶点值运行Marching Tetrahedra会漏掉高维胞的变化. 例如一个四面体的顶点, 边和面都为负, 只有三维内部胞为正. 负子复形是封闭四面体壳, 包含一个空腔; 但等值面算法只看到四个负顶点, 无法识别内部的正胞.
$\\$ 作者把负胞或至少含一个正顶点的胞称为平凡胞. 对合法时间函数, 这类胞的符号能由顶点符号确定. 非平凡胞则自身为正, 顶点全负, 需要细分.
$\\$ 细分从低维向高维进行. 对非平凡胞, 以及含有已细分面的胞, 在胞的质心添加顶点, 再将它与边界面连接. 新建胞继承原胞的时间值, 原有边界胞保留自己的值. 对上面的四面体, 新的正中心点把原本只记录在三维胞上的正值带入顶点数据.
$\\$ 向上处理含已细分面的胞, 是为了让相邻部分共享一致的剖分. 只在每个体胞内部独立插点, 可能留下不匹配的公共面. 细分结束后, 顶点式提取才能读取胞的正负结构.
$\\$ 四面体网格细分后仍由四面体组成. 立方网格会产生含四面体, 立方体和棱锥的混合复形, 论文分别使用对应的提取方法; 对立方体还调整查找表以保留负顶点的6连通约定. 因此输出的拓扑保证依赖细分规则和连通性约定, 不能替换成任意等值面实现后仍默认成立.
12. 目标控制, 代价选择与批量实验
第7节在同一输入上改变目标数量和代价函数, 再用批量目标配置与输入扰动测试成功率.
$\\$ $\cdot$ 目标数量控制: Tree输入包含1个连通分支, 17个通道和1个空腔. 作者移除空腔, 分别保留0, 3, 5, 10个通道, 并用持续图检查留下的是对应数量的高持久度特征. Bone则包含102个分支, 582个通道和57个空腔, 用于测试多类特征的同时控制.
$\\$ $\cdot$ 切割与填充的选择: Tree中同一个局部位置, 会随目标数量改变而采用不同操作. 选择取决于本轮候选之间的冲突和总代价, 所以不能对每个次要特征独立挑选其最便宜的操作, 再假定所有局部选择能一起执行.
$\\$ $\cdot$ 代价函数的影响: Vessel实验比较时间代价, 胞数量代价, 以及偏好切割或填充的设置. 胞数量较少的改动仍可能位于不合适的位置. Helmet是薄壳, 默认时间代价下切割与填充的代价接近, 切割会产生裂缝. 作者改用偏好填充的度量后, 在达到同一目标拓扑的同时避免了这些裂缝.
$\\$ $\cdot$ 目标未知时的辅助判断: Skull实验通过持久度直方图选择阈值, 得到保留33个通道的目标. 这展示了持续同调如何帮助用户选择数量, 并未给出自动识别真实解剖拓扑的保证.
$\\$ 批量实验包括Enzyme与Root上的1500多个目标配置, 以及310个加入扰动后拓扑变复杂的Thingi10K模型. 作者报告这些测试均达到指定拓扑; 连同展示案例, 近2000次测试中只有两次需要第二轮迭代. 这是该测试集上的结果, 不能替代任意输入上的成功性证明.
$\\$ 对比实验采用了不同的输入约束. Zeng等人的方法需要用户提供核心与邻域, 作者为其设置了平凡拓扑目标; Kissi等人的函数简化方法则使用实验中的最高阈值. 比较结果应连同这些设置一起阅读.
13. 计算开销与适用边界
作者使用PHAT计算持续同调, 并用穷尽约化获得规范生成元. 作者观察到, 相比标准约化给出的代表循环, 规范生成元能生成形状更合适的切割和填充. 选择不同的代表链, 会通过骨架改变候选的几何范围.
$\\$ 表1中, Bone的过滤简化耗时157.46秒, 其中PHAT为133.10秒; Root分别为1600.24秒与1448.60秒. 在作者的测试机器上, 持续同调计算占据主要运行时间, 候选选择的开销则很小. 这些测量反映该实现的瓶颈, 不构成整体算法的复杂度证明.
$\\$ 网格分辨率限制了可见特征与候选位置, 切割和填充也可能留下不光滑的离散形状. 作者提出通过局部过滤减少计算量, 在简化中细化网格改善几何等后续方向; 当前实现尚未提供这些能力.
$\\$ 命题5.1负责保证候选的拓扑效果, 命题5.2负责给定候选集合上的选择最优, 第6节处理输出转换. 其中, 我花最多时间核对的是5.1对迁移过程中配对变化的限制.
14. 证明补记: 孤立性与A.3, A.4
A.2(1) 说明, 简单对中的高维胞不能是出生胞. 设简单对为$\{\phi,\sigma\}$, 其中$\phi$是$\sigma$的自由面. 在当前复形中, 只有$\sigma$的边界包含$\phi$. 因此, 无论给包含$\sigma$的链添加哪些同维胞, 都无法抵消边界中的$\phi$, 也就无法得到边界为零的循环. 而出生胞必须包含在它所产生的生成循环中, 所以$\sigma$不可能是出生胞.
$\\$ A.2(2) 说明, 若出生胞$b$在当前过滤前缀$X$中孤立, 则其死亡搭档$d$不属于$X$. 这里的前缀是按过滤顺序已经加入的全部胞, 所以结论是$b \in X$, $d \notin X$, 而不是说$d$在空间上离$b$很远. 可以用反证法理解: 若$d$已经加入, 那么$b$出生时产生的生成循环$z$就已经成为某个高一维链的边界. 由于$z$包含$b$, 这个高一维链中至少要有一个胞, 其边界包含$b$. 这就要求当前复形中存在$b$的上胞, 与$b$孤立矛盾. 因而, 只要$b$在当前复形中仍然孤立, 它所产生的同调类就尚未死亡.
$\\$ A.3把孤立的次要出生胞$b$逐步移到负时间末尾, 再改为正时间. 原文$\sigma^-$, $\sigma^+$分别是最后一个负时间胞和紧随其后的正时间胞; 最后取$0 < f'(b) < f(\sigma^+)$, 不需要越过$\sigma^+$. 孤立性保证途中不会跨过自己的负时间上胞, 所以每一步合法.
途中若端点重新配对, 使用出生胞交换Case 1.1.2. 另一出生胞$c$在过滤顺序中出生更晚, 死亡更早. 由于$f$只要求不减, 这说明其持久度不大于$b$的持久度, 不一定严格更小. 交换后$b$仍孤立, A.2(2) 又要求它接过的死亡搭档为正时间, 因此$c$原来也是活跃配对. 若主要与次要之间没有持久度并列, 即可推出$c$也是次要配对, 换搭档不触及主要配对. 最后改符号, 恰好让$b$当前的一对退出活跃集合; 边界处的并列情形需要另行约定和论证.
$\\$ 每次交换的合法性还可以拆成两个检查. 设$b$后面紧邻的负时间胞为$c$. $c$不可能是$b$的面, 因为原顺序已要求面先于$b$; $c$也不可能是$b$的上胞, 因为$b$在负时间复形中孤立. 因而二者没有面关系, 交换不会破坏过滤顺序. 再把$b$的时间提高到$f(c)$, 时间仍沿新顺序不减. 最后将$b$改成小于首个正时间胞的正值时, 它的面都已在前面, 所有上胞仍在后面, 这一步也合法.
$\\$ Case 1.1.1仍可能更新生成元与余生成元, 只是端点不变. 所以A.3保留主要配对的结论, 不应扩大为保留所有代表链. 死亡顺序影响结果, 是因为约化时先到的死亡事件消去的基底组合不同; 还必须满足原文的代表链包含条件, 不能只比较两个时间.
$\\$ 可以用一个模2主元计算看清两种情况. 设相邻出生胞原来满足$a < b$, 两个死亡胞为$a'$, $b'$. 只看决定主元的$a$, $b$两行, 把其它更早的行略去: 假设$a'$列在这两行上的系数为$(1,0)$, $b'$列为$(1,1)$. 这表示$b'$列同时包含$a$和$b$, 对应这里需要的包含关系. 主元取列中顺序最靠后的非零行; 交换$a$, $b$就改变了这两行谁更靠后.
$\\$ 若$a' < b'$, 先处理$a'$列时, 主元无论交换前后都是$a$. 原顺序下$b'$列以$b$为主元; 交换后它暂时以$a$为主元, 但加上已处理的$a'$列便得到$(0,1)$, 主元仍归$b$. 所以配对仍是$\{a,a'\}$和$\{b,b'\}$, 只是约化使用的链发生变化, 对应Case 1.1.1.
$\\$ 若$b' < a'$, 则先处理含两行的$b'$列. 交换前它以$b$为主元, 交换后以$a$为主元. 随后处理$a'$列: 交换前主元为$a$; 交换后需加上$b'$列消去$a$, 留下$b$. 于是配对由$\{b,b'\}$, $\{a,a'\}$变成$\{a,b'\}$, $\{b,a'\}$, 对应Case 1.1.2. 死亡顺序决定了哪一列能先占用主元, 哪一列必须借助它消元. 这个局部例子解释交换机制, 不能替代一般情形中的生成元包含条件.
$\\$ A.4跟踪端点集合: 次要出生胞集合少$b$, 次要死亡胞集合少最终与$b$配对的$d$, 不一定是它最初的搭档. 这个$d$或者是$b$的上胞, 或者其对偶在最终背景中不孤立. 在A.6中排除这两种情况后, 才能确认后续目标仍属于次要配对.
15. 证明补记: A.5为何保留代表链?
A.5要求简单对$\{\phi,\sigma\}$避开原有全部活跃生成元. 先迁移$\sigma$, 它在离开形状前始终简单, 由A.2(1) 始终为死亡胞. 相关更新只有死亡胞交换Case 2.1.1和2.1.2, 且涉及的死亡胞都为负时间. 结合局部规则只更新相关两对及其指定代表链, 才能推出原有活跃配对不变.
$\\$ 这里不能只凭”两个配对不活跃” 就断言其它代表链不变, 还要核对更新范围. 设交换的死亡胞为$a$, $b$, 对应$\{a^*,a\}$和$\{b^*,b\}$. 因为$a$, $b$都在零时刻之前, 它们的出生胞更早, 所以这两对均不活跃. Case 2.1.1只修改第二对的生成元和第一对的余生成元; Case 2.1.2重新组合这两对的端点, 并更新它们的代表链. 两条规则都不更新第三对. 因而原有活跃配对及其指定代表链不受影响. 这个结论依赖论文列出的局部更新规则, 不是任意重新选取同调基底都具有的性质.
$\\$ $\sigma$变成正时间后临时产生一个活跃配对. 再迁移$\phi$: 它失去唯一上胞, 已经孤立. 若它是出生胞, A.2(2) 排除非活跃配对, 而生成元避让条件排除原有活跃配对, 所以只能与$\sigma$配对; 否则它暂时是死亡胞.
$\\$ $\phi$为死亡胞时, Case 3.1可能让它转为出生胞, 但仍只能配$\sigma$. 配上$\sigma$后, Case 1.1.1要求它进入某个原有活跃生成元, 与前提矛盾; Case 1.1.2会让它配负时间死亡胞, 与孤立性矛盾. 原有活跃代表链因此保持不变.
$\\$ 最后$\phi$与$\sigma$相邻, $\phi$是$\sigma$最后进入的面, $\sigma$是$\phi$第一个进入的上胞. 边界矩阵的$\sigma$列以$\phi$为主元, 此前也没有列能消去该行, 故二者构成配对. 把$\phi$改为正时间就消除临时活跃配对. 正式引理保留的是原有活跃配对及其代表链, 不包括所有非活跃配对.
$\\$ “此前没有列能消去该行” 还包括此前已经约化过的列. 在$\sigma$之前, 没有胞以$\phi$为面, 因而所有原始边界列在$\phi$行的系数都为零. 约化只对这些列做线性组合, 不可能在这一行产生非零值. 而$\sigma$列在$\phi$行非零, 且更靠后的行均为零, 所以它的主元无法与任何先前列的主元相撞. 这里的”已约化” 是指主元已满足配对算法的要求, 不要求把主元上方的非零项也全部消去.
16. 证明补记: A.6的分阶段迁移
令$B$为所选切割的目标出生胞, $D$为所选填充的目标死亡胞. 候选已经限定来自次要配对, 所以$B$不会混入主要配对的目标出生胞. A.6按$C \setminus B$, $F \setminus D$, $B$, $D$的次序证明迁移效果.
$\\$ 生成集合的辅助部分可以按删除次序组织成简单对; 第$i$对只需在前$i – 1$对移除后为简单对. 前两段分别在形状和背景应用A.5, 保留原有活跃配对与代表链. 此时目标胞孤立, 才能逐个应用A.3迁移$B$与$D$.
$\\$ 迁移$B$之后, 还要确认$D$仍由次要配对的死亡胞组成, 且其对偶保持孤立. 对每次迁移的$b \in B$, A.4(2) 说次要死亡胞集合只会少一个胞$e$, 且$e$满足两种条件之一: $e$是$b$的上胞, 或$\widehat e$在迁移后的背景中不孤立. 要证明$d \in D$不会退出, 必须把这两种可能都排除.
$\\$ 第一种可能由切割与填充互不相交排除: $b \in C$, $d \in F$, 所以$d$不可能是$b$的上胞. 第二种可能要先检查背景的变化: 删除形状中的$b$, 就是在对偶背景里加入$\widehat b$. 原来孤立的$\widehat d$只有在新增胞$\widehat b$成为其上胞时才可能失去孤立性; 对偶反转面关系, 这又等价于$d$是$b$的上胞, 已被排除. 因此$d$既不是第一类$e$, 也不是第二类$e$, 仍是次要死亡胞. 每迁移一个$b$都能重复这个检查, 所以结论对整个$B$成立; 但它不保证$d$的出生搭档始终不变.
$\\$ 分阶段迁移改变了$C$, $F$内部顺序. 恢复原顺序所需的相邻交换可以逐个构造: 在某一组内, 找出当前顺序与目标顺序第一次不同的位置, 把目标位置应有的胞$x$从后方逐步向前交换. 设$x$即将跨过的胞为$y$. 当前顺序中$y$在$x$之前, 目标顺序中$x$在$y$之前. 若$y$是$x$的面, 目标顺序就不合法; 若$x$是$y$的面, 当前顺序就不合法. 两个顺序均合法, 所以二者必无面关系, 可以交换. 每完成一轮就多固定一个位置, 有限次后便恢复该组的原相对顺序, 且不必跨越组外的胞.
$\\$ 上述构造只证明顺序合法, 配对不变还需另一条依据: A.4与A.5的迁移论证保证此时$C$, $F$中的胞只涉及非活跃配对. 在各组内部应用局部交换规则, 才能排除对活跃配对的影响. 时间值还须沿恢复后的顺序保持不减, 不能只换顺序却任意保留一组下降的时间值. 实际实现可以跳过这条证明路径, 直接执行第7节的稳定重排.
17. 疑似笔误与引用范围
以下为对照当前论文版本所得的阅读判断, 不代表作者发布的正式勘误.
$\\$ $\cdot$ A.3中描述出生胞交换并改变配对时引用Case 2.1.2, 应为Case 1.1.2. 前者是死亡胞交换规则.
$\\$ $\cdot$ A.6迁移$C \setminus B$与$F \setminus D$时两次引用A.3来保留全部活跃配对及其代表链, 与前提和结论对应的应是A.5. 需要修正引理编号, 而非把结论降为只保留主要配对.
$\\$ $\cdot$ A.5前导文字说保留所有配对, 正式陈述限定为原有活跃配对, 应以后者为准.
$\\$ $\cdot$ A.5迁移$\sigma$时引用Case 2.1.1与2.1.2正确, 因为它此时是死亡胞. 孤立$\phi$不能成为非活跃配对出生胞的论证应引用A.2(2), 也不需改成A.2(1).
18. UE实现例子
出于License限制, 无法放出源码.
