TY - GEN
T1 - Quasi-Universality of Reeb Graph Distances
AU - Bauer, Ulrich
AU - Bjerkevik, Håvard Bakke
AU - Fluhr, Benedikt
N1 - Publisher Copyright:
© Ulrich Bauer, Hvard Bakke Bjerkevik, and Benedikt Fluhr; licensed under Creative Commons License CC-BY 4.0
PY - 2022/6/1
Y1 - 2022/6/1
N2 - 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.
AB - 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.
KW - Reeb graphs
KW - contour trees
KW - distances
KW - functional contortion distance
KW - functional distortion distance
KW - interleaving distance
KW - merge trees
KW - universality
UR - http://www.scopus.com/inward/record.url?scp=85134355209&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2022.14
DO - 10.4230/LIPIcs.SoCG.2022.14
M3 - Conference contribution
AN - SCOPUS:85134355209
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 38th International Symposium on Computational Geometry, SoCG 2022
A2 - Goaoc, Xavier
A2 - Kerber, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th International Symposium on Computational Geometry, SoCG 2022
Y2 - 7 June 2022 through 10 June 2022
ER -