Reconstructing embedded graphs from persistence diagrams
Reconstructing embedded graphs from persistence diagrams
复制标题
从持久性图重建嵌入图
DOI：
10.1016/j.comgeo.2020.101658
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Williams, Lucia
中科院分区：
文献类型：
--
作者：
Belton, Robin Lynne;Fasy, Brittany Terese;Mertz, Rostik;Micka, Samuel;Millman, David L.;Salinas, Daniel;Schenfisch, Anna;Schupbach, Jordan;Williams, Lucia
持久性图（PD）是一种越来越流行的拓扑描述符。通过在不同尺度上对拓扑特征的大小和突出性进行编码，PD提供了关于空间的重要几何和拓扑信息。最近的工作表明，精心选择的（有限）集的PD可以区分几何单纯形复合体，提供了一种方法，用于表示复杂的形状使用一组有限的描述符。一个相关的逆问题是：给定一组PD（或者我们可以查询持久性图的预言），什么是潜在的几何单纯复形？本文提出了一个从n2 − n+ d+ 1个有向（增广）PD重构Rd中n个顶点的嵌入图（R2中的平面图）的算法.此外，我们经验验证的正确性和时间复杂性，我们的算法在R 2随机生成的平面图使用我们的实现，并解释实现我们的算法的数值限制。
The persistence diagram (PD) is an increasingly popular topological descriptor. By encoding the size and prominence of topological features at varying scales, the PD provides important geometric and topological information about a space. Recent work has shown that well-chosen (finite) sets of PDs can differentiate between geometric simplicial complexes, providing a method for representing complex shapes using a finite set of descriptors. A related inverse problem is the following: given a set of PDs (or an oracle we can query for persistence diagrams), what is underlying geometric simplicial complex? In this paper, we present an algorithm for reconstructing embedded graphs in R d (plane graphs in R 2) with n vertices from n 2− n+ d+ 1 directional (augmented) PDs. Additionally, we empirically validate the correctness and time-complexity of our algorithm in R 2 on randomly generated plane graphs using our implementation, and explain the numerical limitations of implementing our algorithm.