Document Open Access Logo

A Family of Metrics from the Truncated Smoothing of Reeb Graphs

Authors Erin Wolf Chambers, Elizabeth Munch , Tim Ophelders

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.22.pdf
  • Filesize: 1.07 MB
  • 17 pages

Document Identifiers

Author Details

Erin Wolf Chambers
  • Department of Computer Science, St. Louis University, MO, USA
Elizabeth Munch
  • Department of Computational Mathematics, Science and Engineering and Department of Mathematics, Michigan State University, East Lansing, MI, USA
Tim Ophelders
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands

Funding

  • Chambers, Erin Wolf: This work was funded in part by the National Science Foundation through grants CCF-1907612 and DBI-1759807.
  • Munch, Elizabeth: This work was funded in part by the National Science Foundation through grants CCF-1907591 and DEB-1904267.
  • Ophelders, Tim: This work was funded in part by the National Science Foundation through grant CCF-1907591.

Acknowledgements

The authors wish to thank the anonymous reviewers for their helpful feedback and insights that tightened the bounds of Theorem 5.3.

Cite As Get BibTex

Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders. A Family of Metrics from the Truncated Smoothing of Reeb Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.22

Abstract

In this paper, we introduce an extension of smoothing on Reeb graphs, which we call truncated smoothing; this in turn allows us to define a new family of metrics which generalize the interleaving distance for Reeb graphs. Intuitively, we "chop off" parts near local minima and maxima during the course of smoothing, where the amount cut is controlled by a parameter τ. After formalizing truncation as a functor, we show that when applied after the smoothing functor, this prevents extensive expansion of the range of the function, and yields particularly nice properties (such as maintaining connectivity) when combined with smoothing for 0 ≤ τ ≤ 2ε, where ε is the smoothing parameter. Then, for the restriction of τ ∈ [0,ε], we have additional structure which we can take advantage of to construct a categorical flow for any choice of slope m ∈ [0,1]. Using the infrastructure built for a category with a flow, this then gives an interleaving distance for every m ∈ [0,1], which is a generalization of the original interleaving distance, which is the case m = 0. While the resulting metrics are not stable, we show that any pair of these for m, m' ∈ [0,1) are strongly equivalent metrics, which in turn gives stability of each metric up to a multiplicative constant. We conclude by discussing implications of this metric within the broader family of metrics for Reeb graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
  • Theory of computation → Computational geometry
Keywords
  • Reeb graphs
  • interleaving distance
  • graphical signatures

Metrics

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

Related Versions

References

  1. Ulrich Bauer, Barbara Di Fabio, and Claudia Landi. An edit distance for Reeb graphs. In A. Ferreira, A. Giachetti, and D. Giorgi, editors, Eurographics Workshop on 3D Object Retrieval. The Eurographics Association, 2016. URL: https://doi.org/10.2312/3dor.20161084.
  2. Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry - SoCG '14, Kyoto, Japan, 2014. Google Scholar
  3. Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb Graph Edit Distance Is Universal. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.15.
  4. Ulrich Bauer, Elizabeth Munch, and Yusu Wang. Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), pages 461-475, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.461.
  5. S. Biasotti, D. Giorgi, M. Spagnuolo, and B. Falcidieno. Reeb graphs for shape analysis and applications. Theoretical Computer Science: Computational Algebraic Geometry and Applications, 392(13):5-22, 2008. URL: https://doi.org/10.1016/j.tcs.2007.10.018.
  6. Håvard Bakke Bjerkevik and Magnus Bakke Botnan. Computational Complexity of the Interleaving Distance. In Bettina Speckmann and Csaba D. Tóth, editors, 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.13.
  7. Håvard Bakke Bjerkevik, Magnus Bakke Botnan, and Michael Kerber. Computing the interleaving distance is NP-hard. Foundations of Computational Mathematics, November 2019. URL: https://doi.org/10.1007/s10208-019-09442-y.
  8. Andrew J. Blumberg and Michael Lesnick. Universality of the homotopy interleaving distance. CoRR, 2017. URL: http://arxiv.org/abs/1705.01690v1.
  9. Magnus Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. Algebraic & Geometric Topology, 18(6):3133-3204, October 2018. URL: https://doi.org/10.2140/agt.2018.18.3133.
  10. Magnus Bakke Botnan, Justin Curry, and Elizabeth Munch. A relative theory of interleavings. CoRR, 2020. URL: http://arxiv.org/abs/2004.14286v1.
  11. Adam Brown, Omer Bobrowski, Elizabeth Munch, and Bei Wang. Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology, December 2020. URL: https://doi.org/10.1007/s41468-020-00063-x.
  12. Peter Bubenik, Vin de Silva, and Jonathan Scott. Metrics for generalized persistence modules. Foundations of Computational Mathematics, 2014. Google Scholar
  13. Peter Bubenik, Vin de Silva, and Jonathan Scott. Interleaving and Gromov-Hausdorff distance. CoRR, 2017. URL: http://arxiv.org/abs/1707.06288v3.
  14. Peter Bubenik and Jonathan A. Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600-627, 2014. URL: https://doi.org/10.1007/s00454-014-9573-x.
  15. 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. URL: https://doi.org/10.1007/978-3-642-40104-6_19.
  16. Mathieu Carrière and Steve Oudot. Local equivalence and intrinsic metrics between Reeb graphs. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1-25:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.25.
  17. Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders. A family of metrics from the truncated smoothing of Reeb graphs. CoRR, 2020. URL: http://arxiv.org/abs/2007.07795v3.
  18. Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas, and Steve Y. Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the 25th annual symposium on Computational geometry, SCG '09, pages 237-246, New York, NY, USA, 2009. ACM. URL: https://doi.org/10.1145/1542362.1542407.
  19. 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. URL: https://doi.org/10.1145/2582112.2582129.
  20. Joshua Cruz. Metric limits in categories with a flow. CoRR, 2019. URL: http://arxiv.org/abs/1901.04828v1.
  21. Justin Curry. Sheaves, Cosheaves and Applications. PhD thesis, University of Pennsylvania, 2014. URL: http://arxiv.org/abs/1303.3255.
  22. Justin Curry and Amit Patel. Classification of constructible cosheaves. CoRR, 2016. URL: http://arxiv.org/abs/1603.01587v5.
  23. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb graphs. Discrete & Computational Geometry, pages 1-53, 2016. URL: https://doi.org/10.1007/s00454-016-9763-9.
  24. Vin de Silva, Elizabeth Munch, and Anastasios Stefanou. Theory of interleavings on categories with a flow. Theory and Applications of Categories, 33(21):583-607, 2018. URL: http://www.tac.mta.ca/tac/volumes/33/21/33-21.pdf.
  25. 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, 2013. URL: https://doi.org/10.1145/2461912.2462017.
  26. Tamal K. Dey and Yusu Wang. Reeb graphs: Approximation and persistence. Discrete & Computational Geometry, 49(1):46-73, 2013. URL: https://doi.org/10.1007/s00454-012-9463-z.
  27. B. Di Fabio and C. Landi. Reeb graphs of curves are stable under function perturbations. Mathematical Methods in the Applied Sciences, 35(12):1456-1471, 2012. URL: https://doi.org/10.1002/mma.2533.
  28. Barbara Di Fabio and Claudia Landi. The edit distance for Reeb graphs of surfaces. Discrete & Computational Geometry, 55(2):423-461, January 2016. URL: https://doi.org/10.1007/s00454-016-9758-6.
  29. 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. URL: https://doi.org/10.1007/978-3-642-40261-6_14.
  30. Elena Farahbakhsh Touli and Yusu Wang. FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 83:1-83:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPICS.ESA.2019.83.
  31. Ellen Gasparovic, Elizabeth Munch, Steve Oudot, Katharine Turner, Bei Wang, and Yusu Wang. Intrinsic interleaving distance for merge trees. CoRR, 2019. URL: http://arxiv.org/abs/1908.00063.
  32. Xiaoyin Ge, Issam I. Safa, Mikhail Belkin, and Yusu Wang. Data skeletonization via Reeb graphs. In J. Shawe-Taylor, R.S. Zemel, P. Bartlett, F.C.N. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 837-845, 2011. Google Scholar
  33. William Harvey and Yusu Wang. Topological landscape ensembles for visualization of scalar-valued functions. In Proceedings of the 12th Eurographics / IEEE - VGTC Conference on Visualization, EuroVis'10, pages 993-1002, Aire-la-Ville, Switzerland, Switzerland, 2010. Eurographics Association. URL: https://doi.org/10.1111/j.1467-8659.2009.01706.x.
  34. Franck Hétroy and Dominique Attali. Topological quadrangulations of closed triangulated surfaces using the Reeb graph. Graphical Models, 65(1-3):131-148, 2003. URL: https://doi.org/10.1016/s1524-0703(03)00005-5.
  35. 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. URL: https://doi.org/10.1145/383259.383282.
  36. Woojin Kim and Facundo Memoli. Stable signatures for dynamic metric spaces via zigzag persistent homology. CoRR, 2017. URL: http://arxiv.org/abs/1712.04064v1.
  37. Woojin Kim, Facundo Mémoli, and Anastasios Stefanou. The metric structure of the formigram interleaving distance. CoRR, 2019. URL: http://arxiv.org/abs/1912.04366v1.
  38. Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-650, 2015. URL: https://doi.org/10.1007/s10208-015-9255-y.
  39. Dmitriy Morozov, Kenes Beketayev, and Gunther Weber. Interleaving distance between merge trees. In Proceedings of TopoInVis, 2013. Google Scholar
  40. Elizabeth Munch and Anastasios Stefanou. The 𝓁 ∞-cophenetic metric for phylogenetic trees as an interleaving distance. In Association for Women in Mathematics Series, pages 109-127. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-030-11566-1_5.
  41. Elizabeth Munch and Bei Wang. Convergence between categorical representations of Reeb space and Mapper. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1-53:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.53.
  42. Mattia Natali, Silvia Biasotti, Giuseppe Patanè, and Bianca Falcidieno. Graph-based representations of point clouds. Graphical Models, 73(5):151-164, 2011. URL: https://doi.org/10.1016/j.gmod.2011.03.002.
  43. Steve Y. Oudot. Persistence Theory: From Quiver Representations to Data Analysis (Mathematical Surveys and Monographs). American Mathematical Society, 2017. Google Scholar
  44. 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
  45. Luis Scoccola. Locally persistent categories andmetric properties of interleaving distances. PhD thesis, Western University, 2020. Google Scholar
  46. 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
  47. Raghavendra Sridharamurthy, Talha Bin Masood, Adhitya Kamakshidasan, and Vijay Natarajan. Edit distance between merge trees. IEEE Transactions on Visualization and Computer Graphics, pages 1-1, 2018. URL: https://doi.org/10.1109/tvcg.2018.2873612.
  48. Anastasios Stefanou. Dynamics on Categories and Applications. PhD thesis, University at Albany, State University of New York, 2018. Google Scholar
  49. Anastasios Stefanou. Tree decomposition of reeb graphs, parametrized complexity, and applications to phylogenetics. Journal of Applied and Computational Topology, February 2020. URL: https://doi.org/10.1007/s41468-020-00051-1.
  50. Andrzej Szymczak. A categorical approach to contour, split and join trees with application to airway segmentation. In V. Pascucci, H. Tricoche, H. Hagen, and J. Tierny, editors, Topological Methods in Data Analysis and Visualization, pages 205-216. Springer, 2011. Google Scholar
  51. G.H. Weber, P.-T. Bremer, and V. Pascucci. Topological landscapes: A terrain metaphor for scientific data. Visualization and Computer Graphics, IEEE Transactions on, 13(6):1416-1423, November 2007. URL: https://doi.org/10.1109/TVCG.2007.70601.
  52. Zoë Wood, Hugues Hoppe, Mathieu Desbrun, and Peter Schröder. Removing excess topology from isosurfaces. ACM Trans. Graph., 23(2):190-208, 2004. URL: https://doi.org/10.1145/990002.990007.
  53. Lin Yan, Yusu Wang, Elizabeth Munch, Ellen Gasparovic, and Bei Wang. A structural average of labeled merge trees for uncertainty visualization. IEEE Transactions on Visualization and Computer Graphics, pages 1-1, 2019. URL: https://doi.org/10.1109/tvcg.2019.2934242.
  54. Hiroki Yuda. Topological smoothing of Reeb graphs. Master’s thesis, St. Louis University, 2019. 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