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.25
URN: urn:nbn:de:0030-drops-160338
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16033/
Chambers, Erin Wolf ;
Parsa, Salman ;
Schreiber, Hannah
On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class
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.
BibTeX - Entry
@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/opus/volltexte/2022/16033},
URN = {urn:nbn:de:0030-drops-160338},
doi = {10.4230/LIPIcs.SoCG.2022.25},
annote = {Keywords: computational topology, bottleneck optimal cycles, homology}
}
|
Keywords: |
|
computational topology, bottleneck optimal cycles, homology |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
