DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.44

Stability and Approximations for Decorated Reeb Spaces

Authors: Justin Curry, Washington Mio, Tom Needham, Osman Berat Okutan, and Florian Russold

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

Abstract

Given a map f:X → M from a topological space X to a metric space M, a decorated Reeb space consists of the Reeb space, together with an attribution function whose values recover geometric information lost during the construction of the Reeb space. For example, when M = ℝ is the real line, the Reeb space is the well-known Reeb graph, and the attributions may consist of persistence diagrams summarizing the level set topology of f. In this paper, we introduce decorated Reeb spaces in various flavors and prove that our constructions are Gromov-Hausdorff stable. We also provide results on approximating decorated Reeb spaces from finite samples and leverage these to develop a computational framework for applying these constructions to point cloud data.

Cite as

Justin Curry, Washington Mio, Tom Needham, Osman Berat Okutan, and Florian Russold. Stability and Approximations for Decorated Reeb Spaces. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{curry_et_al:LIPIcs.SoCG.2024.44,
  author =	{Curry, Justin and Mio, Washington and Needham, Tom and Okutan, Osman Berat and Russold, Florian},
  title =	{{Stability and Approximations for Decorated Reeb Spaces}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{44:1--44:17},
  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.44},
  URN =		{urn:nbn:de:0030-drops-199891},
  doi =		{10.4230/LIPIcs.SoCG.2024.44},
  annote =	{Keywords: Reeb spaces, Gromov-Hausdorff distance, Persistent homology}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2024.51

Efficient Algorithms for Complexes of Persistence Modules with Applications

Authors: Tamal K. Dey, Florian Russold, and Shreyas N. Samaga

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

Abstract

We extend the persistence algorithm, viewed as an algorithm computing the homology of a complex of free persistence or graded modules, to complexes of modules that are not free. We replace persistence modules by their presentations and develop an efficient algorithm to compute the homology of a complex of presentations. To deal with inputs that are not given in terms of presentations, we give an efficient algorithm to compute a presentation of a morphism of persistence modules. This allows us to compute persistent (co)homology of instances giving rise to complexes of non-free modules. Our methods lead to a new efficient algorithm for computing the persistent homology of simplicial towers and they enable efficient algorithms to compute the persistent homology of cosheaves over simplicial towers and cohomology of persistent sheaves on simplicial complexes. We also show that we can compute the cohomology of persistent sheaves over arbitrary finite posets by reducing the computation to a computation over simplicial complexes.

Cite as

Tamal K. Dey, Florian Russold, and Shreyas N. Samaga. Efficient Algorithms for Complexes of Persistence Modules with Applications. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2024.51,
  author =	{Dey, Tamal K. and Russold, Florian and Samaga, Shreyas N.},
  title =	{{Efficient Algorithms for Complexes of Persistence Modules with Applications}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{51:1--51:18},
  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.51},
  URN =		{urn:nbn:de:0030-drops-199969},
  doi =		{10.4230/LIPIcs.SoCG.2024.51},
  annote =	{Keywords: Persistent (co)homology, Persistence modules, Sheaves, Presentations}
}

Search Results

Documents authored by Russold, Florian

Stability and Approximations for Decorated Reeb Spaces

Abstract

Cite as

Efficient Algorithms for Complexes of Persistence Modules with Applications

Abstract

Cite as

Thanks for your feedback!

Could not send message