Document Open Access Logo

Local Equivalence and Intrinsic Metrics between Reeb Graphs

Authors Mathieu Carrière, Steve Oudot

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.25.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Mathieu Carrière
Steve Oudot

Cite As Get BibTex

Mathieu Carrière and Steve Oudot. Local Equivalence and Intrinsic Metrics between Reeb Graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.25

Abstract

As graphical summaries for topological spaces and maps, Reeb graphs are common objects in the computer graphics or topological data analysis literature.  Defining good metrics between these objects has become an important question for applications, where it matters to quantify the extent by which two given Reeb graphs differ. Recent contributions emphasize this aspect, proposing novel distances such as functional distortion or interleaving that are provably more discriminative than the so-called bottleneck distance, being true metrics whereas the latter is only a pseudo-metric. Their main drawback compared to the bottleneck distance is to be comparatively hard (if at all possible) to evaluate. Here we take the opposite view on the problem and show that the bottleneck distance is in fact good enough locally, in the sense that it is able to discriminate a Reeb graph from any other Reeb graph in a small enough neighborhood, as efficiently as the other metrics do. This suggests considering the intrinsic metrics induced by these distances, which turn out to be all globally equivalent. This novel viewpoint on the study of Reeb graphs has a potential impact on applications, where one may not only be interested in discriminating between data but also in interpolating between them.

Subject Classification

Keywords
  • Reeb Graphs
  • Extended Persistence
  • Induced Metrics
  • Topological Data Analysis

Metrics

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

References

  1. P. Agarwal, K. Fox, A. Nath, A. Sidiropoulos, and Y. Wang. Computing the Gromov-Hausdorff Distance for Metric Trees. In Symp. Algo. Comput., 2015. Google Scholar
  2. M. Alagappan. From 5 to 13: Redefining the Positions in Basketball. MIT Sloan Sports Analytics Conference, 2012. Google Scholar
  3. V. Barra and S. Biasotti. 3D Shape Retrieval and Classification using Multiple Kernel Learning on Extended Reeb graphs. The Visual Computer, 30(11):1247-1259, 2014. Google Scholar
  4. U. Bauer, X. Ge, and Y. Wang. Measuring Distance between Reeb Graphs. In Symp. Comput. Geom., pages 464-473, 2014. Google Scholar
  5. U. Bauer, X. Ge, and Y. Wang. Measuring Distance between Reeb Graphs (v2). CoRR, abs/1307.2839v2, 2016. Google Scholar
  6. U. Bauer, E. Munch, and Y. Wang. Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs. In Symp. Comput. Geom., 2015. Google Scholar
  7. S. Biasotti, D. Giorgi, M. Spagnuolo, and B. Falcidieno. Reeb Graphs for Shape Analysis and Applications. Theo. Comp. Sci., 392(1-3):5-22, 2008. Google Scholar
  8. H. Bjerkevik. Stability of Higher Dimensional Interval Decomposable Persistence Modules. CoRR, abs/1609.02086, 2016. Google Scholar
  9. A. Blumberg, I. Gall, M. Mandell, and M. Pancia. Robust Statistics, Hypothesis Testing, and Confidence Intervals for Persistent Homology on Metric Measure Spaces. CoRR, abs/1206.4581, 2012. Google Scholar
  10. D. Burago, Y. Burago, and S. Ivanov. A Course in Metric Geometry, volume 33 of Graduate Studies in Mathematics. AMS, Providence, RI, 2001. Google Scholar
  11. G. Carlsson, V. de Silva, and D. Morozov. Zigzag Persistent Homology and Real-valued Functions. In Symp. Comput. Geom., pages 247-256, 2009. Google Scholar
  12. M. Carrière and S. Oudot. Structure and Stability of the 1-Dimensional Mapper. In Symp. Comput. Geom., volume 51, pages 1-16, 2016. Google Scholar
  13. Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The Structure and Stability of Persistence Modules. Springer, 2016. Google Scholar
  14. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Extending persistence using Poincaré and Lefschetz duality. Found. Comput. Math., 9(1):79-103, 2009. Google Scholar
  15. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb Graphs. Discr. Comput. Geom., 55:854-906, 2016. Google Scholar
  16. B. di Fabio and C. Landi. The Edit Distance for Reeb Graphs of Surfaces. Discrete Computational Geometry, 55(2):423-461, 2016. Google Scholar
  17. M. Gameiro, Y. Hiraoka, and I. Obayashi. Continuation of Point Clouds via Persistence Diagrams. Physica D, 334:118-132, 2016. Google Scholar
  18. X. Ge, I. Safa, M. Belkin, and Y. Wang. Data Skeletonization via Reeb Graphs. In Neural Inf. Proc. Sys., pages 837-845, 2011. Google Scholar
  19. Alexandr Ivanov, Nadezhda Nikolaeva, and Alexey Tuzhilin. The Gromov-Hausdorff Metric on the Space of Compact Metric Spaces is Strictly Intrinsic. Mathematical Notes, 100(6):947-950, 2016. Google Scholar
  20. P. 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(1236), 2013. Google Scholar
  21. W. Mohamed and A. Ben Hamza. Reeb graph path dissimilarity for 3d object matching and retrieval. The Visual Computer, 28(3):305-318, 2012. Google Scholar
  22. T. Mukasa, S. Nobuhara, A. Maki, and T. Matsuyama. Finding Articulated Body in Time-Series Volume Data, pages 395-404. Springer Berlin Heidelberg, 2006. Google Scholar
  23. M. Nicolau, A. Levine, and G. 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 Science, 108(17):7265-7270, 2011. Google Scholar
  24. S. Ohta. Gradient flows on Wasserstein spaces over compact Alexandrov spaces. American Journal Mathematics, 131(2):475-516, 2009. Google Scholar
  25. S. Ohta. Barycenters in Alexandrov spaces of curvature bounded below. Advances Geometry, 12:571-587, 2012. Google Scholar
  26. G. Reeb. Sur les points singuliers d'une forme de pfaff complètement intégrable ou d'une fonction numérique. CR Acad. Sci. Paris, 222:847-849, 1946. Google Scholar
  27. G. Singh, F. Mémoli, and G. Carlsson. Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. In Symp. PB Graphics, 2007. Google Scholar
  28. J. Tierny, J.-P. Vandeborre, and M. Daoudi. Invariant High Level Reeb Graphs of 3D Polygonal Meshes. Symp. 3D Data Proc. Vis. Trans., pages 105-112, 2006. 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