This thesis studies problems in computational topology through the lens of semi-algebraic geometry. We first give an algorithm for computing a semi-algebraic basis for the first homology group, H1(S,F), with coefficients in a field F, of any given semi-algebraic set S⊂Rk defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves s polynomials whose degrees are bounded by d, the complexity of the algorithm is bounded by (sd)<sup>kO</sup><sup>(1)</sup>.This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. We then turn our attention to the Reeb graph, a tool from Morse theory which has recently found use in applied topology due to its ability to track the changes in connectivity of level sets of a function. The roadmap of a set, a construction that arises in semi-algebraic geometry, is a one-dimensional set that encodes information about the connected components of a set. In this thesis, we show that the Reeb graph and, more generally, the Reeb space, of a semi-algebraic set is homeomorphic to a semi-algebraic set, which opens up the algorithmic problem of computing a semi-algebraic description of the Reeb graph. We present an algorithm with singly-exponential complexity that realizes the Reeb graph of a function f:X→Y as a semi-algebraic quotient using the roadmap of X with respect to f.
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/15078906 |
| Date | 29 July 2021 |
| Creators | Sarah B Percival (11205636) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/Efficient_Computation_of_Reeb_Spaces_and_First_Homology_Groups/15078906 |
Page generated in 0.0025 seconds