License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.15
URN: urn:nbn:de:0030-drops-160237
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16023/
Go to the corresponding LIPIcs Volume Portal

Bauer, Ulrich ; Roll, Fabian

Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations

pdf-format:
LIPIcs-SoCG-2022-15.pdf (0.7 MB)

Abstract

Motivated by computational aspects of persistent homology for Vietoris–Rips filtrations, we generalize a result of Eliyahu Rips on the contractibility of Vietoris–Rips complexes of geodesic spaces for a suitable parameter depending on the hyperbolicity of the space. We consider the notion of geodesic defect to extend this result to general metric spaces in a way that is also compatible with the filtration. We further show that for finite tree metrics the Vietoris–Rips complexes collapse to their corresponding subforests. We relate our result to modern computational methods by showing that these collapses are induced by the apparent pairs gradient, which is used as an algorithmic optimization in Ripser, explaining its particularly strong performance on tree-like metric data.

BibTeX - Entry

@InProceedings{bauer_et_al:LIPIcs.SoCG.2022.15,
  author =	{Bauer, Ulrich and Roll, Fabian},
  title =	{{Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{15:1--15:15},
  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/opus/volltexte/2022/16023},
  URN =		{urn:nbn:de:0030-drops-160237},
  doi =		{10.4230/LIPIcs.SoCG.2022.15},
  annote =	{Keywords: Vietoris–Rips complexes, persistent homology, discrete Morse theory, apparent pairs, hyperbolicity, geodesic defect, Ripser}
}

Keywords: Vietoris–Rips complexes, persistent homology, discrete Morse theory, apparent pairs, hyperbolicity, geodesic defect, Ripser
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

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