No description available.

<p>Applied topology is a rapidly growing discipline aiming at using ideas coming from algebraic topology to solve problems in the real world, including analyzing point cloud data, shape analysis, etc. Semi-algebraic geometry deals with studying properties of semi-algebraic sets that are subsets of $\mathbb{R}^n$ and defined in terms of polynomial inequalities. Semi-algebraic sets are ubiquitous in applications in areas such as modeling, motion planning, etc. Developing efficient algorithms for computing topological invariants of semi-algebraic sets is a rich and well-developed field.</p> <p>However, applied topology has thrown up new invariants---such as persistent homology and barcodes---which give us new ways of looking at the topology of semi-algebraic sets. In this thesis, we investigate the interplay between these two areas. We aim to develop new efficient algorithms for computing topological invariants of semi-algebraic sets, such as persistent homology, and to develop new mathematical tools to make such algorithms possible.</p>

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)^kO⁽¹⁾.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.