License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.461
URN: urn:nbn:de:0030-drops-51467
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5146/
Go to the corresponding LIPIcs Volume Portal

Bauer, Ulrich ; Munch, Elizabeth ; Wang, Yusu

Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs

pdf-format:
63.pdf (0.5 MB)

Abstract

The Reeb graph is a construction that studies a topological space through the lens of a real valued function. It has been commonly used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several metrics on the set of Reeb graphs have been proposed. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the Gromov-Hausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a near-isomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. Our result also implies the bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance.

BibTeX - Entry

@InProceedings{bauer_et_al:LIPIcs:2015:5146,
  author =	{Ulrich Bauer and Elizabeth Munch and Yusu Wang},
  title =	{{Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{461--475},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5146},
  URN =		{urn:nbn:de:0030-drops-51467},
  doi =		{10.4230/LIPIcs.SOCG.2015.461},
  annote =	{Keywords: Reeb graph, interleaving distance, functional distortion distance}
}

Keywords: Reeb graph, interleaving distance, functional distortion distance
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI