DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2022.25

On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

Authors: Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber

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

Abstract

Homology features of spaces which appear in applications, for instance 3D meshes, are among the most important topological properties of these objects. Given a non-trivial cycle in a homology class, we consider the problem of computing a representative in that homology class which is optimal. We study two measures of optimality, namely, the lexicographic order of cycles (the lex-optimal cycle) and the bottleneck norm (a bottleneck-optimal cycle). We give a simple algorithm for computing the lex-optimal cycle for a 1-homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3-manifolds of size n² in the Euclidean 3-space, the problem of finding a bottleneck optimal cycle cannot be solved more efficiently than solving a system of linear equations with an n × n sparse matrix. From this reduction, we deduce several hardness results. Most notably, we show that for 3-manifolds given as a subset of the 3-space of size n², persistent homology computations are at least as hard as rank computation (for sparse matrices) while ordinary homology computations can be done in O(n² log n) time. This is the first such distinction between these two computations. Moreover, it follows that the same disparity exists between the height persistent homology computation and general sub-level set persistent homology computation for simplicial complexes in the 3-space.

Cite as

Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber. On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2022.25,
  author =	{Chambers, Erin Wolf and Parsa, Salman and Schreiber, Hannah},
  title =	{{On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-160338},
  doi =		{10.4230/LIPIcs.SoCG.2022.25},
  annote =	{Keywords: computational topology, bottleneck optimal cycles, homology}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.57

Barcodes of Towers and a Streaming Algorithm for Persistent Homology

Authors: Michael Kerber and Hannah Schreiber

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.

Cite as

Michael Kerber and Hannah Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2017.57,
  author =	{Kerber, Michael and Schreiber, Hannah},
  title =	{{Barcodes of Towers and a Streaming Algorithm for Persistent Homology}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.57},
  URN =		{urn:nbn:de:0030-drops-71936},
  doi =		{10.4230/LIPIcs.SoCG.2017.57},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Matrix reduction, Streaming algorithms, Simplicial Approximation}
}

Search Results

Documents authored by Schreiber, Hannah

On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

Abstract

Cite as

Barcodes of Towers and a Streaming Algorithm for Persistent Homology

Abstract

Cite as

Thanks for your feedback!

Could not send message