2 Search Results for "Roll, Fabian"

Document
DOI: 10.4230/LIPIcs.SoCG.2022.15
Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations

Authors: Ulrich Bauer and Fabian Roll

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

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.
Cite as

Ulrich Bauer and Fabian Roll. Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.15},
  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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.58
The Degree-Rips Complexes of an Annulus with Outliers

Authors: Alexander Rolle

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

Abstract
The degree-Rips bifiltration is the most computable of the parameter-free, density-sensitive bifiltrations in topological data analysis. It is known that this construction is stable to small perturbations of the input data, but its robustness to outliers is not well understood. In recent work, Blumberg-Lesnick prove a result in this direction using the Prokhorov distance and homotopy interleavings. Based on experimental evaluation, they argue that a more refined approach is desirable, and suggest the framework of homology inference. Motivated by these experiments, we consider a probability measure that is uniform with high density on an annulus, and uniform with low density on the disc inside the annulus. We compute the degree-Rips complexes of this probability space up to homotopy type, using the Adamaszek-Adams computation of the Vietoris-Rips complexes of the circle. These degree-Rips complexes are the limit objects for the Blumberg-Lesnick experiments. We argue that the homology inference approach has strong explanatory power in this case, and suggest studying the limit objects directly as a strategy for further work.
Cite as

Alexander Rolle. The Degree-Rips Complexes of an Annulus with Outliers. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rolle:LIPIcs.SoCG.2022.58,
  author =	{Rolle, Alexander},
  title =	{{The Degree-Rips Complexes of an Annulus with Outliers}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{58:1--58:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.58},
  URN =		{urn:nbn:de:0030-drops-160664},
  doi =		{10.4230/LIPIcs.SoCG.2022.58},
  annote =	{Keywords: multi-parameter persistent homology, stability, homology inference}
}
  • Refine by Author
  • 1 Bauer, Ulrich
  • 1 Roll, Fabian
  • 1 Rolle, Alexander

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Geometric topology
  • 1 Mathematics of computing → Trees

  • Refine by Keyword
  • 1 Ripser
  • 1 Vietoris–Rips complexes
  • 1 apparent pairs
  • 1 discrete Morse theory
  • 1 geodesic defect
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact