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.2017.25
URN: urn:nbn:de:0030-drops-71794
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7179/
Go to the corresponding LIPIcs Volume Portal

Carrière, Mathieu ; Oudot, Steve

Local Equivalence and Intrinsic Metrics between Reeb Graphs

pdf-format:
LIPIcs-SoCG-2017-25.pdf (0.6 MB)

Abstract

As graphical summaries for topological spaces and maps, Reeb graphs are common objects in the computer graphics or topological data analysis literature. Defining good metrics between these objects has become an important question for applications, where it matters to quantify the extent by which two given Reeb graphs differ. Recent contributions emphasize this aspect, proposing novel distances such as functional distortion or interleaving that are provably more discriminative than the so-called bottleneck distance, being true metrics whereas the latter is only a pseudo-metric. Their main drawback compared to the bottleneck distance is to be comparatively hard (if at all possible) to evaluate. Here we take the opposite view on the problem and show that the bottleneck distance is in fact good enough locally, in the sense that it is able to discriminate a Reeb graph from any other Reeb graph in a small enough neighborhood, as efficiently as the other metrics do. This suggests considering the intrinsic metrics induced by these distances, which turn out to be all globally equivalent. This novel viewpoint on the study of Reeb graphs has a potential impact on applications, where one may not only be interested in discriminating between data but also in interpolating between them.

BibTeX - Entry

@InProceedings{carrire_et_al:LIPIcs:2017:7179,
  author =	{Mathieu Carri{\`e}re and Steve Oudot},
  title =	{{Local Equivalence and Intrinsic Metrics between Reeb Graphs}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7179},
  URN =		{urn:nbn:de:0030-drops-71794},
  doi =		{10.4230/LIPIcs.SoCG.2017.25},
  annote =	{Keywords: Reeb Graphs, Extended Persistence, Induced Metrics, Topological Data Analysis}
}

Keywords: Reeb Graphs, Extended Persistence, Induced Metrics, Topological Data Analysis
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

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