Document Open Access Logo

Graph Reconstruction by Discrete Morse Theory

Authors Tamal K. Dey, Jiayuan Wang, Yusu Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.31.pdf
  • Filesize: 1.47 MB
  • 15 pages

Document Identifiers

Author Details

Tamal K. Dey
Jiayuan Wang
Yusu Wang

Cite As Get BibTex

Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Graph Reconstruction by Discrete Morse Theory. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.31

Abstract

Recovering hidden graph-like structures from potentially noisy data is a fundamental task in modern data analysis. Recently, a persistence-guided discrete Morse-based framework to extract a geometric graph from low-dimensional data has become popular. However, to date, there is very limited theoretical understanding of this framework in terms of graph reconstruction. This paper makes a first step towards closing this gap. Specifically, first, leveraging existing theoretical understanding of persistence-guided discrete Morse cancellation, we provide a simplified version of the existing discrete Morse-based graph reconstruction algorithm. We then introduce a simple and natural noise model and show that the aforementioned framework can correctly reconstruct a graph under this noise model, in the sense that it has the same loop structure as the hidden ground-truth graph, and is also geometrically close. We also provide some experimental results for our simplified graph-reconstruction algorithm.

Subject Classification

Keywords
  • graph reconstruction
  • discrete Morse theory
  • persistence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Aanjaneya, F. Chazal, D. Chen, M. Glisse, L. Guibas, and D. Morozov. Metric graph reconstruction from noisy data. International Journal of Computational Geometry &Applications, 22(04):305-325, 2012. Google Scholar
  2. D. Attali, M. Glisse, S. Hornus, F. Lazarus, and D. Morozov. Persistence-sensitive simplification of functions on surfaces in linear time. Presented at TOPOINVIS, 9:23-24, 2009. Google Scholar
  3. U. Bauer, C. Lange, and M. Wardetzky. Optimal topological simplification of discrete functions on surfaces. Discr. Comput. Geom., 47(2):347-377, 2012. Google Scholar
  4. S. Biasotti, D. Giorgi, M. Spagnuolo, and B. Falcidieno. Reeb graphs for shape analysis and applications. Theoretical Computer Science, 392(1-3):5-22, 2008. Google Scholar
  5. F. Chazal, R. Huang, and J. Sun. Gromov-hausdorff approximation of filamentary structures using reeb-type graphs. Discr. Comput. Geom., 53(3):621-649, 2015. Google Scholar
  6. O. Delgado-Friedrichs, V. Robins, and A. Sheppard. Skeletonization and partitioning of digital images using discrete morse theory. IEEE Trans. Pattern Anal. Machine Intelligence, 37(3):654-666, March 2015. Google Scholar
  7. T. Dey and J. Sun. Defining and computing curve-skeletons with medial geodesic function. In Sympos. Geom. Proc., volume 6, pages 143-152, 2006. Google Scholar
  8. T. Dey, J. Wang, and Y. Wang. Improved road network reconstruction using discrete morse theory. In Proc. 25th ACM SIGSPATIAL. ACM, 2017. Google Scholar
  9. T. Dey, J. Wang, and Y. Wang. Graph reconstruction by discrete morse theory. arXiv preprint arXiv:1803.05093, 2018. Google Scholar
  10. H. Edelsbrunner and J. Harer. Computational Topology - an Introduction. American Mathematical Soc., 2010. URL: http://www.ams.org/bookstore-getitem/item=MBK-69.
  11. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discr. Comput. Geom., 28:511-533, 2002. Google Scholar
  12. The ENZO project. URL: http://enzo-project.org.
  13. The Center for Integrative Biomedical Computing (CIBC). Micro-CT Dataset Archive. URL: https://www.sci.utah.edu/cibc-software/cibc-datasets.html.
  14. R. Forman. Morse theory for cell complexes. Advances in mathematics, 134(1):90-145, 1998. Google Scholar
  15. X. Ge, I. I Safa, M. Belkin, and Y. Wang. Data skeletonization via reeb graphs. In Advances in Neural Info. Proc. Sys., pages 837-845, 2011. Google Scholar
  16. A. Gyulassy, M. Duchaineau, V. Natarajan, V. Pascucci, E. Bringa, A. Higginbotham, and B. Hamann. Topologically clean distance fields. IEEE Trans. Visualization Computer Graphics, 13(6):1432-1439, Nov 2007. Google Scholar
  17. T. Hastie and W. Stuetzle. Principal curves. Journal of the American Statistical Association, 84(406):502-516, 1989. Google Scholar
  18. B. Kégl and A. Krzyzak. Piecewise linear skeletonization using principal curves. IEEE Trans. Pattern Anal. Machine Intelligence, 24(1):59-74, 2002. Google Scholar
  19. L. Liu, E. W Chambers, D. Letscher, and T. Ju. Extended grassfire transform on medial axes of 2d shapes. Computer-Aided Design, 43(11):1496-1505, 2011. Google Scholar
  20. J. Milnor. Morse Theory. Princeton Univ. Press, New Jersey, 1963. Google Scholar
  21. M. Natali, S. Biasotti, G. Patanè, and B. Falcidieno. Graph-based representations of point clouds. Graphical Models, 73(5):151-164, 2011. Google Scholar
  22. U. Ozertem and D. Erdogmus. Locally defined principal curves and surfaces. Journal of Machine learning research, 12(Apr):1249-1286, 2011. Google Scholar
  23. V. Robins, P. J. Wood, and A. P. Sheppard. Theory and algorithms for constructing discrete morse complexes from grayscale digital images. IEEE Trans. Pattern Anal. Machine Intelligence, 33(8):1646-1658, Aug 2011. Google Scholar
  24. T. Sousbie. The persistent cosmic web and its filamentary structure-i. theory and implementation. Monthly Notices of the Royal Astronomical Society, 414(1):350-383, 2011. Google Scholar
  25. S. Wang, Y. Wang, and Y. Li. Efficient map reconstruction and augmentation via topological methods. In Proc. 23rd ACM SIGSPATIAL, page 25. ACM, 2015. Google Scholar
  26. Y. Yan, K. Sykes, E. Chambers, D. Letscher, and T. Ju. Erosion thickness on medial axes of 3d shapes. ACM Trans. on Graphics, 35(4):38, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact