DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.15

Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory

Authors: Ulrich Bauer and Fabian Roll

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

We study the connection between discrete Morse theory and persistent homology in the context of shape reconstruction methods. Specifically, we consider the construction of Wrap complexes, introduced by Edelsbrunner as a subcomplex of the Delaunay complex, and the construction of lexicographic optimal homologous cycles, also considered by Cohen–Steiner, Lieutier, and Vuillamy in a similar setting. We show that for any cycle in a Delaunay complex for a given radius parameter, the lexicographically optimal homologous cycle is supported on the Wrap complex for the same parameter, thereby establishing a close connection between the two methods. We obtain this result by establishing a fundamental connection between reduction of cycles in the computation of persistent homology and gradient flows in the algebraic generalization of discrete Morse theory.

Cite as

Ulrich Bauer and Fabian Roll. Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2024.15,
  author =	{Bauer, Ulrich and Roll, Fabian},
  title =	{{Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.15},
  URN =		{urn:nbn:de:0030-drops-199600},
  doi =		{10.4230/LIPIcs.SoCG.2024.15},
  annote =	{Keywords: persistent homology, discrete Morse theory, apparent pairs, Wrap complex, lexicographic optimal chains, shape reconstruction}
}

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.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}
}

Search Results

Documents authored by Roll, Fabian

Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message