The topological features of an object are features which are preserved while continuously deforming the object. Examples are the dimension of an object and the number of holes in it. In contrast, the geometric features of an object such as its volume can dramatically change under such deformations. The robustness of topological features makes them more appealing for analyzing objects in the presence of noise, which is inevitable in practice. Researchers in various areas such as topological data analysis, computer graphics, visualization, and sensor networks have shown an increased need for efficient algorithms for computing topological features. Such demands inspire the work in this dissertation.
The general framework of topological methods for computing topological features from point cloud data usually contains two necessary steps: constructing simplicial complexes and applying algebraic topology techniques on the simplicial complexes (e.g., persistent homology). The first part of this dissertation investigates these two steps and contributes new efficient tools. The investigation into the first step led to a simplicial complex called the graph induced complex, which offers several advantages over other practically favored simplicial complexes such as Vietoris-Rips and witness complexes. The graph induced complex is small in size but still carries various topological information of the underlying space from which the point data are sampled. Moreover, it is highly effective to use the graph induced complex for inferring the first dimensional homology.
Our investigation into the second step produced two efficient algorithms for computing topological persistence for simplicial maps. Our new algorithms generalize the traditional persistent homology algorithm which is limited to the filtration that is a sequence of nested spaces with respect to the inclusion (a special simplicial map). Since simplicial maps occur naturally in practice, our algorithms increase the practical power of persistent homology.
In addition to studying general tools for topological methods, this dissertation also develops efficient algorithms for computing two topological features, the intrinsic dimension of a manifold in Rn and the handle and tunnel loops of a surface in R3. Treated as a topological feature, the intrinsic dimension m of a manifold embedded in Rn can be recovered from its local homology which is isomorphic to the reduced homology of an m-dimensional sphere. Based on this property, an efficient purely topological method for detecting the intrinsic dimension of a manifold from its sampled points is developed in our work. Specifically, our method computes the local homology of a manifold from its samples exactly which in turn gives the intrinsic dimension of the manifold.
Finally, this dissertation proposes an efficient algorithm for computing a topological feature of closed surfaces in R3 called handle and tunnel loops. Previous methods for computing handle and tunnel loops of a closed surface require the explicit knowledge of the interior and exterior bounded by the surface. By using the concepts of Reeb graphs and linking numbers, the new method eliminates this limitation. Moreover, experimental results show that our method for computing handle and tunnel loops is significantly faster than previous methods.