Document Open Access Logo

Convergence between Categorical Representations of Reeb Space and Mapper

Authors Elizabeth Munch, Bei Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.53.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Elizabeth Munch
Bei Wang

Cite As Get BibTex

Elizabeth Munch and Bei Wang. Convergence between Categorical Representations of Reeb Space and Mapper. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.53

Abstract

The Reeb space, which generalizes the notion of a Reeb graph, is one of the few tools in topological data analysis and visualization suitable for the study of multivariate scientific datasets. First introduced by Edelsbrunner et al., it compresses the components of the level sets of a multivariate mapping and obtains a summary representation of their relationships. A related construction called mapper, and a special case of the mapper construction called the Joint Contour Net have been shown to be effective in visual analytics. Mapper and JCN are intuitively regarded as discrete approximations of the Reeb space, however without formal proofs or approximation guarantees. An open question has been proposed by Dey et al. as to whether the mapper construction converges to the Reeb space in the limit. 

In this paper, we are interested in developing the theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis. Using tools from category theory, we formally prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations. Given a sequence of refined discretizations, we prove that these approximations converge to the Reeb space in the interleaving distance; this also helps to quantify the approximation quality of the discretization at a fixed resolution.

Subject Classification

Keywords
  • Topological data analysis
  • Reeb space
  • mapper
  • category theory

Metrics

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

References

  1. Peter Bubenik, Vin de Silva, and Jonathan Scott. Metrics for generalized persistence modules. Foundations of Computational Mathematics, 15(6):1501-1531, 2015. Google Scholar
  2. Hamish Carr and David Duke. Joint contour nets. IEEE Transactions on Visualization and Computer Graphics, 20(8):1100-1113, 2014. Google Scholar
  3. Hamish Carr, Jack Snoeyink, and Michiel van de Panne. Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree. Computational Geometry, 43:42-58, 2010. Google Scholar
  4. Mathieu Carriére and Steve Oudot. Structure and stability of the 1-dimensional mapper. Symposium on Computational Geometry (to appear); arXiv:1511.05823, 2016. Google Scholar
  5. Frédéric Chazal and Jian Sun. Gromov-Hausdorff approximation of filament structure using Reeb-type graph. Proceedings 13th Annual Symposium on Computational Geometry, pages 491-500, 2014. Google Scholar
  6. Justin Curry. Sheaves, Cosheaves and Applications. PhD thesis, University of Pennsylvania, 2014. Google Scholar
  7. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorification of Reeb graphs. Discrete and Computational Geometry (to appear); arXiv:1501.04147, 2016. Google Scholar
  8. Tamal K. Dey, Facundo Mémoli, and Yusu Wang. Mutiscale mapper: A framework for topological summarization of data and maps. arXiv:1504.03763, 2015. Google Scholar
  9. Herbert Edelsbrunner and John Harer. Jacobi sets of multiple Morse functions. In F. Cucker, R. DeVore, P. Olver, and E. Süli, editors, Foundations of Computational Mathematics, Minneapolis 2002, pages 37-57. Cambridge University Press, 2002. Google Scholar
  10. Herbert Edelsbrunner, John Harer, and Amit K. Patel. Reeb spaces of piecewise linear mappings. Proceedings 24th Annual Symposium on Computational Geometry, pages 242-250, 2008. Google Scholar
  11. William Harvey, Yusu Wang, and Rephael Wenger. A randomized O(mlogm) algorithm for computing Reeb graphs of arbitrary simplicial complexes. ACM Symposium on Computational Geometry, pages 267-276, 2010. Google Scholar
  12. Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. Google Scholar
  13. Dimitry Kozlov. Combinatorial Algebraic Topology. Springer, 2008. Google Scholar
  14. P. Y. Lum, G. Singh, A. Lehman, T. Ishkanov, M. Vejdemo-Johansson, M. Alagappan, J. Carlsson, and G. Carlsson. Extracting insights from the shape of complex data using topology. Scientific Reports, 3, 2013. Google Scholar
  15. Saunders Mac Lane. Categories for the Working Mathematician. Springer-Verlag, New York, NY, 2nd edition, 1978. Google Scholar
  16. Elizabeth Munch and Bei Wang. Convergence between categorical representations of Reeb space and mapper. arXiv:1307.7760, 2016. Google Scholar
  17. Monica Nicolaua, Arnold J. Levineb, and Gunnar Carlsson. Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival. Proceedings National Academy of Sciences of the United States of America, 108(17):7265-7270, 2011. Google Scholar
  18. Salman Parsa. A deterministic O(mlogm) time algorithm for the Reeb graph. Proceedings 29th Annual Symposium on Computational Geometry, pages 269-276, 2012. Google Scholar
  19. Amit Patel. Reeb Spaces and the Robustness of Preimages. PhD thesis, Duke University, 2010. Google Scholar
  20. Michael A. Penna. On the geometry of combinatorial manifolds. Pacific Journal of Mathematics, 77(2):499-522, 1978. Google Scholar
  21. G. Reeb. Sur les points singuliers d'une forme de pfaff completement intergrable ou d'une fonction numerique [on the singular points of a complete integral pfaff form or of a numerical function]. Comptes Rendus Acad.Science Paris, 222:847-849, 1946. Google Scholar
  22. Gurjeet Singh, Facundo Mémoli, and Gunnar Carlsson. Topological methods for the analysis of high dimensional data sets and 3D object recognition. In Eurographics Symposium on Point-Based Graphics, 2007. Google Scholar
  23. Roar Bakken Stovner. On the mapper algorithm: A study of a new topological method for data analysis. Master’s thesis, Norwegian University of Science and Technology, 2012. Google Scholar
  24. Jon Woolf. The fundamental category of a stratified space. arXiv:0811.2580, 2013. 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