Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations
Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations
复制标题
词典最优同源链及其在点云三角剖分中的应用
DOI：
10.1007/s00454-022-00432-6
复制
发表时间：
2019
影响因子：
0.8
通讯作者：
J. Vuillamy
中科院分区：
文献类型：
--
作者：
D. Cohen;A. Lieutier;J. Vuillamy
本文考虑了整数模2系数的最优同源链问题（OHCP）的一个特殊情况，其中最优性是指链上的最小字典序是由单形上的总序引起的。使用持久同调的矩阵约简算法推导出求解该问题实例的多项式算法，而OHCP在经典情况下是np困难的。当简单复形为伪流形时，利用对偶图最小割公式将复杂度进一步提高到拟线性算法。然后，我们通过在点云三角测量的上下文中提供一个应用程序来展示这个问题的特定实例是如何相关的。
This paper considers a particular case of the Optimal Homologous Chain Problem (OHCP) for integer modulo 2 coefficients, where optimality is meant as a minimal lexicographic order on chains induced by a total order on simplices. The matrix reduction algorithm used for persistent homology is used to derive polynomial algorithms solving this problem instance, whereas OHCP is NP-hard in the classical setting. The complexity is further improved to a quasilinear algorithm by leveraging a dual graph minimum cut formulation when the simplicial complex is a pseudomanifold. We then show how this particular instance of the problem is relevant, by providing an application in the context of point cloud triangulation.