LIPIcs.SoCG.2022.14.pdf
- Filesize: 0.72 MB
- 18 pages
Document
Quasi-Universality of Reeb Graph Distances
Authors
Ulrich Bauer 
,
Håvard Bakke Bjerkevik ,
Benedikt Fluhr
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
File
Document Identifiers
Author Details
- Department of Mathematics and Munich Data Science Institute, Technische Universität München, Germany
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
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)
0PDF Downloads
References
- Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-universality of Reeb graph distances. Preprint, 2021. URL: http://arxiv.org/abs/2112.00720.
-
Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. In Computational geometry (SoCG'14), pages 464-473. ACM, New York, 2014.
- 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.
- 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.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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/.
-
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.
- 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.
- 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.
- 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.