2026-08-11T02:58:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16033 2024-03-06T10:56:47Z ddc:004 open_access

On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class Chambers, Erin Wolf Parsa, Salman Schreiber, Hannah computational topology bottleneck optimal cycles homology 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erin Wolf Chambers and Salman Parsa and Hannah Schreiber 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.25 urn:nbn:de:0030-drops-160338 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.25 eng https://creativecommons.org/licenses/by/4.0/legalcode