DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2022.14

Quasi-Universality of Reeb Graph Distances

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

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2022.14,
  author =	{Bauer, Ulrich and Bjerkevik, H\r{a}vard Bakke and Fluhr, Benedikt},
  title =	{{Quasi-Universality of Reeb Graph Distances}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.14},
  URN =		{urn:nbn:de:0030-drops-160221},
  doi =		{10.4230/LIPIcs.SoCG.2022.14},
  annote =	{Keywords: Reeb graphs, contour trees, merge trees, distances, universality, interleaving distance, functional distortion distance, functional contortion distance}
}

Search Results

Documents authored by Fluhr, Benedikt

Quasi-Universality of Reeb Graph Distances

Abstract

Cite as

Thanks for your feedback!

Could not send message