Document Open Access Logo

Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs

Authors Ulrich Bauer, Elizabeth Munch, Yusu Wang

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.461.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Ulrich Bauer
Elizabeth Munch
Yusu Wang

Cite As Get BibTex

Ulrich Bauer, Elizabeth Munch, and Yusu Wang. Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 461-475, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.461

Abstract

The Reeb graph is a construction that studies a topological space through the lens of a real valued function.  It has been commonly used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several metrics on the set of Reeb graphs have been proposed. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the Gromov-Hausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a near-isomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. Our result also implies the bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance.

Subject Classification

Keywords
  • Reeb graph
  • interleaving distance
  • functional distortion distance

Metrics

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

References

  1. Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, New York, NY, USA, 2014. ACM. Google Scholar
  2. Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, and Bianca Falcidieno. Reeb graphs for shape analysis and applications. Theoretical Computer Science, 392(1-3):5-22, February 2008. Google Scholar
  3. Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, and Frank Staals. Trajectory grouping structure. In Frank Dehne, Roberto Solis-Oba, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, volume 8037 of Lecture Notes in Computer Science, pages 219-230. Springer Berlin Heidelberg, 2013. Google Scholar
  4. Frédéric Chazal and Jian Sun. Gromov-Hausdorff approximation of filament structure using Reeb-type graph. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 491:491-491:500, New York, NY, USA, 2014. ACM. Google Scholar
  5. Justin Curry. Sheaves, Cosheaves and Applications. PhD thesis, University of Pennsylvania, December 2014. Google Scholar
  6. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb graphs, January 2015. Google Scholar
  7. Tamal K. Dey, Fengtao Fan, and Yusu Wang. An efficient computation of handle and tunnel loops via Reeb graphs. ACM Trans. Graph., 32(4):32:1-32:10, July 2013. Google Scholar
  8. Barbara Di Fabio and Claudia Landi. The edit distance for Reeb graphs of surfaces, November 2014. URL: http://arxiv.org/abs/1411.1544.
  9. Harish Doraiswamy and Vijay Natarajan. Output-Sensitive construction of Reeb graphs. Visualization and Computer Graphics, IEEE Transactions on, 18(1):146-159, January 2012. Google Scholar
  10. Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. Amer. Math. Soc., Providence, Rhode Island, 2010. Google Scholar
  11. Francisco Escolano, Edwin R. Hancock, and Silvia Biasotti. Complexity fusion for indexing Reeb digraphs. In Richard Wilson, Edwin Hancock, Adrian Bors, and William Smith, editors, Computer Analysis of Images and Patterns, volume 8047 of Lecture Notes in Computer Science, pages 120-127. Springer Berlin Heidelberg, 2013. Google Scholar
  12. Xiaoyin Ge, Issam I. Safa, Mikhail Belkin, and Yusu Wang. Data skeletonization via Reeb graphs. Advances in Neural Information Processing Systems, 24:837-845, 2011. Google Scholar
  13. William Harvey, Yusu Wang, and Rephael Wenger. A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. In Proceedings of the Twenty Sixth Annual Symposium on Computational Geometry, SoCG'10, pages 267-276, New York, NY, USA, 2010. ACM. Google Scholar
  14. Franck Hétroy and Dominique Attali. Topological quadrangulations of closed triangulated surfaces using the Reeb graph. Graphical Models, 65(1-3):131-148, May 2003. Google Scholar
  15. Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu L. Kunii. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, SIGGRAPH'01, pages 203-212, New York, NY, USA, 2001. ACM. Google Scholar
  16. Ernest Michael. Continuous selections II. Annals of Mathematics, 64(3):pp. 562-580, 1956. Google Scholar
  17. Dmitriy Morozov, Kenes Beketayev, and Gunther Weber. Interleaving distance between merge trees. Manuscript, 2013. Google Scholar
  18. Mattia Natali, Silvia Biasotti, Giuseppe Patanè, and Bianca Falcidieno. Graph-based representations of point clouds. Graphical Models, 73(5):151-164, September 2011. Google Scholar
  19. Monica Nicolau, Arnold J. Levine, and Gunnar Carlsson. Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival. Proceedings of the National Academy of Sciences, 108(17):7265-7270, 2011. Google Scholar
  20. Salman Parsa. A deterministic O(m log m) time algorithm for the Reeb graph. Discrete & Computational Geometry, 49(4):864-878, 2013. Google Scholar
  21. Georges Reeb. Sur les points singuliers d'une forme de Pfaff complèment intégrable ou d'une fonction numérique. Comptes Rendus de L'Académie ses Séances, 222:847-849, 1946. Google Scholar
  22. Dus̆an Repovs̆ and Pavel V. Semenov. Continuous Selections of Multivalued Mappings. Kluwer Academic Publishers, 1998. Google Scholar
  23. Yoshihisa Shinagawa, Tosiyasu L. Kunii, and Yannick L. Kergosien. Surface coding based on Morse theory. IEEE Comput. Graph. Appl., 11(5):66-78, September 1991. Google Scholar
  24. 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
  25. Zoë Wood, Hugues Hoppe, Mathieu Desbrun, and Peter Schröder. Removing excess topology from isosurfaces. ACM Transactions on Graphics, 23(2):190-208, April 2004. Google Scholar
  26. Yuan Yao, Jian Sun, Xuhui Huang, Gregory R. Bowman, Gurjeet Singh, Michael Lesnick, Leonidas J. Guibas, Vijay S. Pande, and Gunnar Carlsson. Topological methods for exploring low-density states in biomolecular folding pathways. The Journal of Chemical Physics, 130:144115, 2009. 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