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 nontrivial 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 lexoptimal cycle) and the bottleneck norm (a bottleneckoptimal cycle). We give a simple algorithm for computing the lexoptimal cycle for a 1homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3manifolds of size n² in the Euclidean 3space, 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 3manifolds given as a subset of the 3space 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 sublevel set persistent homology computation for simplicial complexes in the 3space.
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:125:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16033},
URN = {urn:nbn:de:0030drops160338},
doi = {10.4230/LIPIcs.SoCG.2022.25},
annote = {Keywords: computational topology, bottleneck optimal cycles, homology}
}
01.06.2022
Keywords: 

computational topology, bottleneck optimal cycles, homology 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 