Document Open Access Logo

Quasi-Universality of Reeb Graph Distances

Authors Ulrich Bauer , Håvard Bakke Bjerkevik , Benedikt Fluhr

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.14.pdf
  • Filesize: 0.72 MB
  • 18 pages

Document Identifiers

Author Details

Ulrich Bauer
  • Department of Mathematics and Munich Data Science Institute, Technische Universität München, Germany
Håvard Bakke Bjerkevik
  • Institute of Geometry, Technische Universität Graz, Austria
Benedikt Fluhr
  • Department of Mathematics, Technische Universität München, Germany

Funding

  • Bauer, Ulrich: DFG SFB/TRR 109 Discretization in Geometry and Dynamics.
  • Bjerkevik, Håvard Bakke: Austrian Science Fund (FWF) grant number P 33765-N.

Cite AsGet BibTex

Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-Universality of Reeb Graph Distances. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.14

Abstract

We establish bi-Lipschitz bounds certifying quasi-universality (universality up to a constant factor) for various distances between Reeb graphs: the interleaving distance, the functional distortion distance, and the functional contortion distance. The definition of the latter distance is a novel contribution, and for the special case of contour trees we also prove strict universality of this distance. Furthermore, we prove that for the special case of merge trees the functional contortion distance coincides with the interleaving distance, yielding universality of all four distances in this case.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Geometric topology
  • Mathematics of computing → Trees
  • Theory of computation → Computational geometry
Keywords
  • Reeb graphs
  • contour trees
  • merge trees
  • distances
  • universality
  • interleaving distance
  • functional distortion distance
  • functional contortion distance

Metrics

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

Related Versions

References

  1. Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-universality of Reeb graph distances. Preprint, 2021. URL: http://arxiv.org/abs/2112.00720.
  2. Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. In Computational geometry (SoCG'14), pages 464-473. ACM, New York, 2014. Google Scholar
  3. Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. Extended version of conference paper, 2016. URL: http://arxiv.org/abs/1307.2839v2.
  4. Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb graph edit distance is universal. Found. Comput. Math., 21(5):1441-1464, 2021. URL: https://doi.org/10.1007/s10208-020-09488-3.
  5. 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, volume 34 of LIPIcs. Leibniz Int. Proc. Inform., pages 461-475. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015. Google Scholar
  6. Robert Cardona, Justin Curry, Tung Lam, and Michael Lesnick. The universal 𝓁^p-metric on merge trees. Preprint, 2021. URL: http://arxiv.org/abs/2112.12165.
  7. Michele d'Amico, Patrizio Frosini, and Claudia Landi. Natural pseudo-distance and optimal matching between reduced size functions. Acta Appl. Math., 109(2):527-554, 2010. URL: https://doi.org/10.1007/s10440-008-9332-1.
  8. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb graphs. Discrete Comput. Geom., 55(4):854-906, 2016. URL: https://doi.org/10.1007/s00454-016-9763-9.
  9. Masaki Hilaga, Yoshihisa Shinagawa, Taku Komura, and Tosiyasu L. Kunii. Topology matching for fully automatic similarity estimation of 3d shapes. In Lynn Pocock, editor, Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2001, Los Angeles, California, USA, August 12-17, 2001, pages 203-212. ACM, 2001. URL: https://doi.org/10.1145/383259.383282.
  10. Dmitriy Morozov, Kenes Beketayev, and Gunther Weber. Interleaving distance between merge trees. Presented at TopoInVis'13. Manuscript, 2013. URL: https://www.mrzv.org/publications/interleaving-distance-merge-trees/.
  11. Georges Reeb. Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique. C. R. Acad. Sci. Paris, 222:847-849, 1946. Google Scholar
  12. Luis N. Scoccola. Locally persistent categories and metric properties of interleaving distances. PhD thesis, The University of Western Ontario, 2020. URL: https://ir.lib.uwo.ca/etd/7119.
  13. Yoshihisa Shinagawa and Tosiyasu L. Kunii. Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications, 11(6):44-51, 1991. URL: https://doi.org/10.1109/38.103393.
  14. Gurjeet Singh, Facundo Mémoli, and Gunnar E. Carlsson. Topological methods for the analysis of high dimensional data sets and 3d object recognition. In Mario Botsch, Renato Pajarola, Baoquan Chen, and Matthias Zwicker, editors, 4th Symposium on Point Based Graphics, PBG@Eurographics 2007, Prague, Czech Republic, September 2-3, 2007, pages 91-100. Eurographics Association, 2007. URL: https://doi.org/10.2312/SPBG/SPBG07/091-100.
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 Imprint Privacy Contact