×

Reconstructing embedded graphs from persistence diagrams. (English) Zbl 1476.68271

Summary: 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 \(\mathbb{R}^d\) (plane graphs in \(\mathbb{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 \(\mathbb{R}^2\) on randomly generated plane graphs using our implementation, and explain the numerical limitations of implementing our algorithm.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
55N31 Persistent homology and applications, topological data analysis
68R10 Graph theory (including graph drawing) in computer science
68U03 Computational aspects of digital topology
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmed, M.; Karagiorgou, S.; Pfoser, D.; Wenk, C., Map construction algorithms, (Map Construction Algorithms (2015), Springer), 1-14 · Zbl 1344.68002
[2] Ahmed, M.; Wenk, C., Constructing street networks from GPS trajectories, (European Symposium on Algorithms - ESA ’12 (2012), Springer), 60-71 · Zbl 1365.68433
[3] Belton, R. L.; Fasy, B. T.; Mertz, R.; Micka, S.; Millman, D. L.; Salinas, D.; Schenfisch, A.; Schupbach, J.; Williams, L., Learning simplicial complexes from persistence diagrams, (Canadian Conference on Computational Geometry - CCCG ’18 (2018)), Also available at
[4] Boots, B.; Okabe, A.; Sugihara, K., Spatial tessellations, (Geographical Information Systems, vol. 1 (1999)), 503-526
[5] Chambers, E. W.; Ju, T.; Letscher, D.; Li, M.; Topp, C. N.; Yan, Y., Some heuristics for the homological simplification problem, (Canadian Conference on Computational Geometry - CCCG ’18 (2018))
[6] Chenavier, N.; Devillers, O., Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity, Adv. Appl. Probab., 50, 35-56 (2018) · Zbl 1431.60012
[7] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 103-120 (2007) · Zbl 1117.54027
[8] Cohen-Steiner, D.; Edelsbrunner, H.; Morozov, D., Vines and vineyards by updating persistence in linear time, (Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (2006), ACM), 119-126 · Zbl 1153.68388
[9] Crawford, L.; Monod, A.; Chen, A. X.; Mukherjee, S.; Rabadán, R., Predicting clinical outcomes in glioblastoma: an application of topological and functional data analysis, J. Am. Stat. Assoc., 1-12 (2019)
[10] Curry, J.; Mukherjee, S.; Turner, K., How many directions determine a shape and other sufficiency results for two topological transforms (2018)
[11] Devillers, O.; Noizet, L., Walking in a planar Poisson-Delaunay triangulation: shortcuts in the Voronoi path, Int. J. Comput. Geom. Appl., 1-12 (2018) · Zbl 1434.60130
[12] Dey, T. K.; Wang, J.; Wang, Y., Graph reconstruction by discrete Morse theory, (34th International Symposium on Computational Geometry, vol. 99. 34th International Symposium on Computational Geometry, vol. 99, SoCG 2018 (2018)), Article 31 pp. · Zbl 1494.55009
[13] Edelsbrunner, H.; Harer, J., Computational Topology: An Introduction (2010), American Mathematical Society · Zbl 1193.55001
[14] Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 511-533 (2002) · Zbl 1011.68152
[15] Fasy, B. T.; Micka, S.; Millman, D. L.; Schenfisch, A.; Williams, L., Challenges in reconstructing shapes from Euler characteristic curves, (Fall Workshop on Computational Geometry - FWCG ’18 (2018))
[16] Fasy, B. T.; Micka, S.; Millman, D. L.; Schenfisch, A.; Williams, L., Persistence diagrams for efficient simplicial complex reconstruction (2019)
[17] Ge, X.; Safa, I. I.; Belkin, M.; Wang, Y., Data skeletonization via Reeb graphs, (Advances in Neural Information Processing Systems - NIPS ’11 (2011)), 837-845
[18] Ghrist, R.; Levanger, R.; Mai, H., Persistent homology and Euler integral transforms, J. Appl. Comput. Topol., 2, 55-60 (2018) · Zbl 1461.58006
[19] Giusti, C.; Pastalkova, E.; Curto, C.; Itskov, V., Clique topology reveals intrinsic geometric structure in neural correlations, Proc. Natl. Acad. Sci., 112, 13455-13460 (2015) · Zbl 1355.92015
[20] Hofer, C.; Kwitt, R.; Niethammer, M.; Uhl, A., Deep learning with topological signatures, (Advances in Neural Information Processing Systems (2017)), 1634-1644
[21] Jones, E.; Oliphant, T.; Peterson, P., SciPy: open source scientific tools for Python (2001)
[22] Karagiorgou, S.; Pfoser, D., On vehicle tracking data-based road network generation, (Proceedings of the 20th International Conference on Advances in Geographic Information Systems - SIGSPATIAL ’12 (2012), ACM), 89-98
[23] Kégl, B.; Krzyzak, A.; Linder, T.; Zeger, K., Learning and design of principal curves, IEEE Trans. Pattern Anal. Mach. Intell., 22, 281-297 (2000)
[24] Lee, Y.; Barthel, S. D.; Dłotko, P.; Moosavi, S. M.; Hess, K.; Smit, B., Quantifying similarity of pore-geometry in nanoporous materials, Nat. Commun., 8, Article 15396 pp. (2017)
[25] Micka, S., Algorithms to Find Topological Descriptors for Shape Reconstruction and How to Search Them (2020), Montana State University, Ph.D. thesis
[26] Millman, D. L.; Verma, V., A slow algorithm for computing the Gabriel graph with double precision, (Canadian Conference on Computational Geometry - CCCG ’11 (2011))
[27] Morozov, D., Dionysus, a c++ library for computing persistent homology (2007)
[28] Oudot, S.; Solomon, E., Inverse problems in topological persistence (2018)
[29] Rizvi, A. H.; Camara, P. G.; Kandror, E. K.; Roberts, T. J.; Schieren, I.; Maniatis, T.; Rabadan, R., Single-cell topological RNA-seq analysis reveals insights into cellular differentiation and development, Nat. Biotechnol., 35, 551 (2017)
[30] Turner, K.; Mukherjee, S.; Boyer, D. M., Persistent homology transform for modeling shapes and surfaces, Inf. Inference, 3, 310-344 (2014) · Zbl 06840289
[31] Zheng, Y.; Gu, S.; Edelsbrunner, H.; Tomasi, C.; Benfey, P., Detailed reconstruction of 3D plant root shape, (Proceedings of the IEEE International Conference on Computer Vision (2011)), 2026-2033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.