PhD, University of Cincinnati, 2024, Engineering and Applied Science: Computer Science and Engineering

Topological Data Analysis (TDA) explores the topological properties of data treated as a topological space. Persistent Homology (PH) is a component of TDA that computes the topological features (connected components, loops, voids, and their higher-dimensional counterparts) found in data. Unfortunately, computing PH in dimensional spaces above R7 is impractical due to the size and computational cost of generating the filtration (filtered complexes) of the data. While there are many types of complexes, they are typically classified into two broad categories, namely: (i) the purely combinatorial Abstract complexes, and (ii) Geometric complexes that have a realization/embedding in a given space. In general, Abstract complexes are relatively easy to generate but suffer from exponential memory growth, making them memory inefficient in higher dimensions and for big data. In contrast, Geometric complexes generally have a significantly more compact representation but their construction incurs significant computational costs that become impractical in higher dimensions. This dissertation works to address the computational and memory costs experienced in the construction of filtered complexes used by TDA algorithms. In particular, this study will examine two main approaches to build a filtered complex of data, namely: (i) the construction of approximate geometric sparsified simplicial complexes for high dimensional and big data, and (ii) the construction and use of approximate Polytopal Complexes where convex polytopes represent cells in the different dimensions of the data. The overall objective of this work is to investigate techniques for quickly constructing geometric complexes that are memory efficient and suitable for use with higher dimensional big data than currently possible. Although several techniques for the sparsification of simplicial complexes are well known, this work contributes a solution based on ß-skeletons (open full item for complete abstract)

Committee: Philip Wilsey Ph.D. (Committee Chair); Vikram Ravindra Ph.D. (Committee Member); Bledar Konomi Ph.D. (Committee Member); Ali Minai Ph.D. (Committee Member); Badri Vellambi Ravisankar Ph.D. (Committee Member) Subjects: Computer Engineering

Doctor of Philosophy, The Ohio State University, 2020, Computer Science and Engineering

The growing need to understand and process data has driven innovation in many disparate areas of data science. The computational biology, graphics, and machine learning communities, among others, are striving to develop robust and efficient methods for such analysis. In this work, we demonstrate the utility of topological data analysis (TDA), a new and powerful tool to understand the shape and structure of data, to these diverse areas. First, we develop a new way to use persistent homology, a core tool in topological data analysis, to extract machine learning features for image classification. Our work focuses on improving modern image classification techniques by considering topological features. We show that incorporating this information to supervised learning models allows our models to improve classification, thus providing evidence that topological signatures can be leveraged for enhancing some of the pioneering applications in computer vision. Next, we propose a topology based, fast, scalable, and parameter-free technique to explore a related problem in protein analysis and classification. On an initial simplicial complex built using constituent protein atoms and bonds, simplicial collapse is used to construct a filtration which we use to compute persistent homology. This is ultimately our signature for the protein-molecules. Our method, besides being scalable, shows sizable time and memory improvements compared to similar topology-based approaches. We use the signature to train a protein domain classifier and compare state-of-the-art structure-based protein signatures to achieve a substantial improvement in accuracy. Besides considering the intervals of persistent homology like our first two applications, some applications need to find representative cycles for them. These cycles, especially the minimal ones, are useful geometric features functioning as augmentations for the intervals in a purely topological barcode. We address the problem of computing th (open full item for complete abstract)

Committee: Tamal Dey (Advisor); Yusu Wang (Committee Member); Raphael Wenger (Committee Member) Subjects: Computer Engineering; Computer Science

PhD, University of Cincinnati, 2023, Engineering and Applied Science: Computer Science and Engineering

Topological Data Analysis (TDA) is a field of data mining that captures the algebraic structure of data by employing topological invariants. Topological invariants are measurable properties of a space such as the cardinality, connectedness, countability, or homology. These characteristics can identify data relationships not found through traditional data analysis methods, providing a unique perspective into the underlying structural representations. Persistent Homology (PH) stands out as a key tool of TDA, as it examines the emergence and collapse of homology classes persisting over a topological filtration. PH yields a set of persistence intervals representing crucial features in the data, including connected components, loops, voids, and higher-dimensional structures that are irreducible through algebraic reduction. Persistent homology has proven effectiveness in data study of various domains, including network analysis, bioinformatics, image recognition, and object classification. However, the memory complexity of PH inhibits study of higher-order homology features, leading to bounded analysis in practice. Applications employing PH have been limited to identifying connected components, loops, and voids, which correspond to the first three dimensions of homology classes. Higher-order homology classes exhibit exponential space complexities relative to both the size and dimension of the data, posing a significant limitation in their study. The Euler Characteristic (EC) detects the general presence of homology classes in a topological space. When the EC is computed over a topological filtration it captures the alternating sum of homology classes, related to the results of PH. This metric, known as the Euler Characteristic Curve (ECC), has found application in several prominent instances of TDA. While the ECC does not identify the distinct individual topological features, it is more memory-efficient than PH and can characterize specific filtration ranges (open full item for complete abstract)

Committee: Philip Wilsey Ph.D. (Committee Chair); Gowtham Atluri Ph.D. (Committee Member); Badri Vellambi Ravisankar Ph.D. (Committee Member); Wen-Ben Jone Ph.D. (Committee Member); Alex Dempsey Ph.D. (Committee Member) Subjects: Computer Engineering

Doctor of Philosophy, The Ohio State University, 2023, Mathematics

Given a metric space $(X,d_X)$, the $n$-th curvature set is the set of $n$-by-$n$ distance matrices generated by a sample from $X$ with $n$ or less points. Similarly, the $(n,k)$ persistence set of $X$ is the set of $k$-dimensional persistence diagrams of all $n$-point samples from $X$. This dissertation has two major parts, each dedicated to persistence sets or curvature sets. A major obstacle that hampers the widespread use of topological techniques in data science is the sometimes prohibitive computational cost of persistent homology. Persistence sets aim to circumvent this limitation while retaining useful geometric and topological information from the input space. We study the experimental and theoretical properties of persistence sets, and compare them with the standard VR-persistent homology from the perspectives of computational efficiency and discriminative power, including in a practical shape classification task. We characterize several persistence sets of the circle, higher-dimensional spheres, surfaces with constant curvature, and a specific family of metric graphs, and show spaces that have different persistence sets but are indistinguishable by persistent homology. All in all, we believe that persistence sets can aid in data science tasks where the shape is important but the standard persistent homology algorithms are impractical. In the second part, we study the curvature sets $\Kn_n(\Sp^1)$ of the circle $\Sp^1$ as a topological space. We give several characterizations of $\Kn_n(\Sp^1)$ as quotients of tori under group actions, and use them to compute the homology of $\Kn_n(\Sp^1)$ with Mayer-Vietoris arguments. We construct an abstract simplicial complex $\St_n(\Sp^1)$ whose geometric realization is $\Kn_n(\Sp^1)$. Moreover, we give an embedding of $\St_n(\Sp^1)$ in $\R^{n \times n}$ and show that $\Kn_n(\Sp^1)$ is the union of the convex hulls of the faces this embedding. Lastly, inspired by the characterization of a persistence set of su (open full item for complete abstract)

Committee: Facundo Mémoli (Advisor); Matthew Kahle (Committee Member); David Anderson (Committee Member) Subjects: Mathematics

Doctor of Philosophy (Ph.D.), Bowling Green State University, 2023, Statistics

Topological data analysis (TDA) has become a popular approach in recent years to study the shape structure of data. Persistence homology is a widely used TDA tool that describes how topology changes through a nested sequence of topological spaces in the form of simplicial complexes. As a result, topological features (e.g., connected components, loops, and voids) appear and disappear, and the summary of this evolution is reported as a persistence diagram (PD). Considered as topological signatures of the data, the space of PDs can be endowed with Wasserstein distance with a stability property. However, since PDs are not vectors in Euclidean space and calculating Wasserstein distances might get computationally costly, they have limitations to be represented as inputs in machine learning tasks. A common remedy to deal with this issue is to map PDs into a space of functions and to vectorized by evaluating them over a grid of scale values which results in vector summaries belonging to Euclidean space. The Betti function, which has incorporated weights, is one of the simplest functional summaries for PDs leading to such vector representations. Even though it is the easiest to construct and fast to implement, no stability result is proven to the best of our knowledge. In the present work, we introduce a new method to vectorize the Betti function by integrating it between two consecutive scale values of a grid. The resulting vector summary, named a vector of averaged Bettis (VAB), provides a lower-dimensional, informative, and computationally efficient vector representation compared to the standard method of vectorizing the Betti function. We also prove a stability result for a class of weight functions with respect to Wasserstein distance. Further, through several experimental studies, we show that the permutation-based hypothesis testing procedure, which aims at identifying whether two sets PDs are drawn from the same distribution or process, can be improved i (open full item for complete abstract)

Committee: Umar Islambekov Ph.D. (Committee Chair); Paul Morris Ph.D. (Other); Kit Chan Ph.D. (Committee Member); Maria Rizzo Ph.D. (Committee Member) Subjects: Statistics

Doctor of Philosophy, The Ohio State University, 2022, Mathematics

We study the theoretical foundation of the persistent topology of the geometric filtrations in Topological Data Analysis (TDA), such as Vietoris--Rips simplicial complexes, Vietoris--Rips metric thickenings. We introduce a $\ell_p$-relaxation to the Vietoris--Rips metric thickening where $p=\infty$ recovers the usual Vietoris--Rips metric thickening. We prove a stability theorem for the persistent homology of $\ell_p$ relaxed metric thickenings, which is novel even in the case $p=\infty$. The stability theorem then can be employed to show that the filtrations by Vietoris--Rips simplicial complexes and Vietoris--Rips metric thickenings have the same persistent diagram. Therefore, we can employ measure-theoretical methods to study the Vietoris--Rips complex. Some recent study also suggests that the persistent homology of Vietoris--Rips simplicial complex changes when the scale passes the diameter of some extremal configuration of the diameter functional. As an example, we study the extremal configurations on spheres. We implemented the diameter gradient flow and obtained nontrivial extremal configurations on $\Sp^2$ and $\Sp^3$. We find a natural condition for metric spaces that will guarantee the vanishing of the persistence diagram of Vietoris--Rips filtration over certain dimensions. We also demonstrate by a non-collapsing result that the persistent features can be utilized to obtain a quantitive lower bound for the Gromov--Hausdorff distance between Riemannian manifolds.

Committee: Facundo Mémoli (Advisor); Jean-François Lafont (Committee Member); Matthew Kahle (Committee Member) Subjects: Mathematics

MS, University of Cincinnati, 2021, Engineering and Applied Science: Computer Science

Topological Data Analysis (TDA) is a relatively recent development in the field of data mining that extends algebraic topology into the realm of computational data mining. TDA has unique advantages compared to other data mining techniques, namely that it is noise resistant and that it generates unique identifiers in the form of persistence intervals for any d-dimensional numerical data set where d>1. These data sets are commonly referred to as point clouds. Persistent homology is a one of the most widely used methods of TDA. Persistent homology is a computational process that creates a multi-dimensional topological representation of an input point cloud. Computing persistent homology is exponential in time and memory relative to the size of the input point cloud. TDA with persistent homology's primary drawback from being widely adopted as a data mining technique is its constraints on point cloud size and dimension. Due to the exponential nature of computing persistent homology, state of the art tools are currently limited to a few thousand points in 3 dimensions and smaller point clouds in higher dimensions (unless the computation is somehow limited to lower dimensional homologies and bounded connectivity distances). This thesis explores techniques to sample larger point clouds to enable the computation of persistent homology. Several techniques to sample large point clouds have been explored. Studies to sample using random or heuristic methods are well established. More recently, the k-means++ clustering algorithm has been used to create reduced mappings (samplings) of the data. These approaches use the k-means++ algorithm to locate a collection of nano-clusters with their centroids being used/extracted to represent the data by a smaller set of points. The number of nano-clusters requested is determined to be of a size such that persistent homology can be computed. While it is known that k-means++ clustering can be used in this way and (open full item for complete abstract)

Committee: Philip Wilsey Ph.D. (Committee Chair); Gowtham Atluri Ph.D. (Committee Member); Wen-Ben Jone Ph.D. (Committee Member) Subjects: Computer Science

MS, University of Cincinnati, 2020, Engineering and Applied Science: Computer Engineering

In an era of increasing data size and complexity novel algorithms to mine embedded relationships within big data are being studied throughout high performance computing. One such approach, Topological Data Analysis (TDA), studies homologies in a point cloud. Identified homologies represent topological features --- loops, holes, and voids --- independent of continuous deformation and resilient to noise. These topological features identify a generalized structure of input data. TDA has shown promise in several applications including studying various networks, digital images and movies, protein analysis and classification, and genomic sequences. TDA provides an alternative approach to classification for general data mining applications. The principle tool of TDA that examines the topological structures in a point cloud is Persistent Homology. Persistent homology identifies the underlying homologies of the point cloud as the connectedness of the point cloud increases, or persists. The output of persistent homology can be used to classify embedded structures in high dimensional spaces, enable automated classification from connected component analysis, identify abnormalities in data streams, classify structure of protein chains, along with many other science and biological applications. Although the uses are vast, persistent homology suffers from exponential growth in both run-time and memory complexity leading to limitations for evaluating large datasets. Persistent homology cannot be directly applied to large point clouds; modern tools are limited to the analysis of a few thousand points in R3. Optimization of data structures and enhancements to the algorithm have led to significant performance improvements, but the approaches still suffer in relation to the size of the input point cloud. One approach studied over recent years is to reduce the input point cloud, either in size or dimensions. These reductions gain obvious improvemen (open full item for complete abstract)

Committee: Philip Wilsey Ph.D. (Committee Chair); Gowtham Atluri Ph.D. (Committee Member); Wen-Ben Jone Ph.D. (Committee Member) Subjects: Computer Engineering

PhD, University of Cincinnati, 2020, Engineering and Applied Science: Computer Science and Engineering

Persistent homology is a robust and powerful tool for data analysis that provides information about topological properties of data. Given a set of data points, persistent homology computes a set of intervals or lifespans of certain topological structures that appear and subsequently disappear through a sequence of nested spaces constructed on the data points. The topological structures and their lifespans enable the segregation of meaningful patterns from noise and often lead to the discovery of insight not discernible by conventional methods of data mining. The capabilities of persistent homology come at the cost of its high space complexity that grows exponentially with the number of input data points. This dissertation examines the application of persistent homology to streaming data, two important but disjoint areas of data science that never crossed paths before. The intensive computational requirements of persistent homology coupled with the unique challenges of dealing with a potentially infinite sequence of data objects in a stream are the primary reasons why persistent homology has not yet been applied to data stream mining. The dissertation proposes two general-purpose frameworks or models, called the microcluster model and the sliding-window model, for computing persistent homology on streaming data. Consistent with the standard computational paradigm for processing data streams, each of the models is organized into online and offline components. The online component maintains a summary of the data that preserves the topological structure of the stream. The offline component computes the persistence intervals from the data captured by the summary. The internal difference between the two models lies in the data structure used to maintain the summary of the stream during the online component. While the microcluster model employs statistics related to the weighted sum of the data vectors, the sliding-window model uses a topological structure that compr (open full item for complete abstract)

Committee: Philip Wilsey Ph.D. (Committee Chair); Gowtham Atluri Ph.D. (Committee Member); Raj Bhatnagar Ph.D. (Committee Member); Brian Gettelfinger Ph.D. (Committee Member); Badri Vellambi Ravisankar Ph.D. (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2020, Mathematics

We refine the theoretical foundations of Topological Data Analysis (TDA) for the multiscale analysis of dynamic topology, such as dynamic metric spaces or dynamic networks. Motivations include, but are not limited to, the characterization of flocking or swarming behavior of animals and social networks in the human sphere. In order to quantify the differences of such dynamics, we also generalize the Gromov-Hausdorff distance. We not only examine the resulting metric geometry, but also find practical algorithms for approximating those novel distances. To establish our results, we primarily exploit concepts from algebraic topology, metric geometry, combinatorics, and category theory, blending these with ideas of persistence in TDA. More specifically, the main achievements of this thesis include (a) The development of stable and informative invariants that encode spatiotemporal topological features of dynamic metric spaces and dynamic networks, (b) The establishment of a comparison framework for dynamic metric spaces or dynamic networks by extending the Gromov-Hausdorff distance or the Gromov-Wasserstein distance, (c) Generalization of the erosion distance by Patel for quantifying within polynomial time the difference between dynamic metric spaces or more generally multiparameter persistence modules, and (d) Extension of the notion of persistence diagram for summarizing persistence modules over posets, which often arise from dynamic data, from a standpoint of combinatorics and category theory.

Committee: Facundo Mémoli (Advisor) Subjects: Mathematics

Master of Mathematical Sciences, The Ohio State University, 2019, Mathematical Sciences

Many problems in science and engineering involve signal analysis. Engineers and scientists came up with many approaches to study signals. Recently, researchers propose a new frame- work, combining the time-delay embedding with the tools from computational topology, for the study of periodic signals. By applying time-delay embedding to the periodic signals, the periodic behaviors express themselves as topological cycles and we can use persistent homol- ogy to detect these topological features. In this thesis, we apply this method to analyze road network data, specifically vehicle flow data recorded by detectors placed on highways. First, we apply time-delay embedding to project the vehicle flow data into point cloud data in a high dimensional space. Then, we use persistent homology tools to detect the topological features and get persistence digram. Next, we can repeat the same experiment to vehicle flow data of different period. Fox example, in our experiment, we use the vehicle flow data of different weeks and months. Therefore, we get persistence diagrams corresponding to the vehicle flow data of different period. Finally, we calculate the bottleneck distance and wasserstein distance between these persistence diagrams and do hierarchical clustering. The dendrograms of the hierarchical clustering show us the patterns behind these vehicle flow data.

Committee: Facundo Mémoli (Advisor); Yusu Wang (Advisor) Subjects: Mathematics

Doctor of Philosophy, The Ohio State University, 2019, Mathematics

Network data, which shows the relationships between entities in complex systems, is becoming available at an ever-increasing rate. In particular, advances in data acquisition and computational power have shifted the bottleneck in analyzing weighted and directed network datasets towards the domain of available mathematical methods. Thus there is a pressing need to develop mathematical foundations for analyzing such datasets. In this thesis, we present methods for applying one of the flagship tools of topological data analysis---persistent homology---to weighted, directed network datasets. We ground these methods in a network distance that had appeared in a restricted context in earlier literature, and is now fully developed in this thesis. This development independently provides metric methods for network data analysis, including and invoking methods from optimal transport. In our framework, a network dataset is represented as a set of points (equipped with the minimalistic structure of a first countable topological space) and a (continuous) real-valued edge weight function. With this terminology, a finite network dataset is viewed as a finite sample from some infinite underlying process---a compact network. This perspective is especially appropriate for data streams that are so large that they are "essentially infinite", or are perhaps being generated continuously in time. We show that the space of all compact networks is the completion of the space of all finite networks. We develop the notion of isomorphism in this space, and explore a range of different geodesics that exist in this space. We develop sampling theorems and explain their use in obtaining probabilistic convergence guarantees. Several persistent homology methods---notably including persistent path homology---are also developed. By virtue of the sampling theorems, we are able to define these methods even for infinite networks. Our theoretical contributions are complemented by software pa (open full item for complete abstract)

Committee: Facundo Mémoli (Advisor) Subjects: Mathematics

Master of Mathematical Sciences, The Ohio State University, 2019, Mathematical Sciences

Quantifying similarity between shapes is an important task in many disciplines, such as architecture, anatomy, security, and manufacturing. My research project is motivated by taxonomic studies in Biology. Taxonomy is the classification of biological organisms based on shared characteristics. In this thesis, we will explore two approaches, based on optimal transport and persistent homology, to discriminating shapes through defining a meaningful distance that reflects geometric or topological features of the shapes under study. By approximating lower bounds to the Gromov-Wasserstein distance and the Gromov-Hausdorff distance, we automate the process of taxon classification by comparing geometric or topological features of anatomical surfaces. We test our implementations on a data set containing surfaces of crowns of teeth that are from primates and non-primates close relatives.

Committee: Facundo Mémoli (Advisor); Tom Needham (Advisor); Janet Best (Committee Member) Subjects: Mathematics

Doctor of Philosophy, The Ohio State University, 2018, Computer Science and Engineering

Shape analysis has been applied in many applications across a broad range of domains. Among various different families of ``complex'' shapes, the ones with 1D non-linear topological structures (skeletons) are particularly interesting. These shapes are simple, as they can be decomposed into 1-d pieces, but still informative in representing the connectivity and other important information behind data. In this thesis, I focus on two objects from computational topology that have been useful for modeling the skeleton of data: the Reeb graph (and its variants) and the 1-(un)stable manifold from discrete Morse theory, and study their properties as well as applications to shape analysis. The two specific topological objects that I focus on have both already been widely used in practical applications. Further theoretical understanding and applications of these two objects in modeling and studying the skeleton of data will be provided. The first part of the dissertation work concerns the so-called Reeb graph and its loop-free variant, the contour tree, which can be used to provide a 1D tree summary of an input scalar field. It has been commonly used in computer graphics and visualization. I have investigated one problem regarding to the theoretical understanding of the contour tree, as well as developing a variant of the Reeb graph to address the issue of noise. Carr et. al. has proposed an algorithm for computing the contour tree for a piece-wise linear function defined on a simplicial complex domain. This algorithm is simple, efficient and has been widely used in practice. However, the algorithm is often applied even when the output contour tree may not exist, in which case the algorithm may not terminate or exit with only partial output. My work provides new understanding of this contour tree algorithm and characterizes the cause for such behavior. I also propose a simple variation of the contour tree (called JS-graph) to handle this situation in p (open full item for complete abstract)

Committee: Yusu Wang (Advisor); Rephael Wenger (Committee Member); Tamal Dey (Committee Member) Subjects: Computer Engineering; Computer Science; Geographic Information Science; Neurosciences

Doctor of Philosophy, The Ohio State University, 2017, Computer Science and Engineering

Topological data analysis (TDA) provides a new methodology to data analysis problems. It captures intrinsic topological structures in data, which can then offer useful guidelines for other data analysis approaches. One main task in TDA is to extract topological features from data. And this is often done through one of the main tools of TDA, persistent homology, or simply, persistence. While the idea of persistent homology has been demonstrated valuable in a broad range of areas, its application to large scale real-world data is limited by the efficiency of existing persistence computation approaches. I will present a focused study during my PhD research on broadening applicability of the idea of persistence in data analysis in two fronts, to explore novel ways of applying persistent homology for qualitative data analysis and to study the computational issues related to persistent homology, so as to significantly broaden their applications to large-scale low or high dimensional data analysis. In the first direction, we applied persistent homology to a special kind of data, called \emph{metric graphs}. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. Thus, comparing two graphs has many important applications in data analysis. In this work, we proposed a new distance between two finite metric graphs, called the \spdist{} distance, which formulates the graph matching problem through persistent homology. Our \spdist{} distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a \emph{continuous} distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our \spdist{} distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous (open full item for complete abstract)

Committee: Tamal Dey Dr. (Advisor); Wang Yusu Dr. (Advisor); Wenger Rephael Dr. (Committee Member); Bozanic Zahn Dr. (Committee Member) Subjects: Computer Science

Master of Mathematical Sciences, The Ohio State University, 2017, Mathematical Sciences

We use the reflection functors introduced by Bernstein, Gelfand, and Ponomarev to define a metric on the space of all zigzag modules of a given length, which we call the reflection distance. We show that the reflection distance between two given zigzag modules of the same length is an upper bound for the bottleneck distance between the persistence diagrams of the given modules. We also extend our distance to weighted zigzag modules and prove an analogous result in this setting.

Committee: Facundo Mémoli Dr. (Advisor); Matthew Kahle Dr. (Committee Member) Subjects: Mathematics

Doctor of Philosophy, The Ohio State University, 2013, Computer Science and Engineering

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 (open full item for complete abstract)

Committee: Tamal Dey (Advisor); Yusu Wang (Advisor); Rephael Wenger (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2012, Mathematics

Persistence theory discussed in this thesis is an application of algebraic topology (Morse Theory) to Data Analysis, precisely to qualitative description of point cloud data. Mathematically a point cloud data is a finite metric space of a very large cardinality. It can be geometrized as a filtration of simplicial complexes and the homology changes of these complexes provide qualitative information about the data. There are new invariants which permit to describe the changes in homology and these invariants are the “bar codes”. In Chapter 3 work is done to develop additional methods for the calculation of bar codes and their refinements. When the coefficient field is Z_2, the calculation of bar codes is done by ELZ algorithm (named after H. Edelsbrunner, D. Letscher, and A. Zomorodian). When the coefficient field is R, we developed an algorithm based on the Hodge decomposition. The original persistence theory can be viewed as a sort of Morse Theory and involves the “sub level sets” of a nice map. With Dan Burghelea and Tamal Dey we developed a persistence theory about level sets in Chapter 4. This is a refinement of the original persistence. The level persistence is an alternative to Zigzag persistence considered by G. Carlsson and V. D. Silva. I discuss new computable invariants and how they are related to the known ones. These invariants are referred to as “relevant level persistence numbers” and “positive and negative bar codes”. We provide enhancements and modifications of ELZ algorithm to calculate such invariants and illustrate them by examples. Chapters 3 and Chapter 4 are preceded by background materials (Chapter 2) where the concepts of algebraic topology used in this paper are defined.

Committee: Dan Burghelea (Advisor); Zig Fiedorowicz (Committee Member); Yusu Wang (Committee Member); Alan Saalfeld (Committee Member) Subjects: Mathematics

Doctor of Philosophy, The Ohio State University, 2010, Computer Science and Engineering

Tunnels are very important topological features of surfaces. In computer graphics, processing tunnels is important for surface parameterization, feature identification, and topological simplification. Tunnels can be represented by loops, circles wrapping around the tunnels. In this dissertation, we will first focus on defining and computing a special set of non-trivial loops called handle and tunnel loops in surfaces embedded in 3D. We show that a closed surface M of genus g always has g handle and g tunnel loops induced by the embedding in 3D. We then propose two algorithms to compute them that are useful in practice: a linking-based algorithm and a persistence-based algorithm. Our linking-based algorithm works on a class of shapes that retract to graphs. We characterize handle and tunnel loops by a linking condition with these graphs. These characterizations lead to algorithms for detection and generation of these loops. We also provide an implementation with applications in feature detection and topology simplification to show the effectiveness of this method. Our second algorithm is a novel application of the concepts from persistent homology in computational topology. It computes topologically correct handle and tunnel loops that are also geometrically relevant. Compared with previous algorithms, this method works combinatorially and doesn't require any extra data structures. Moreover, it is time efficient and can be applied on a large class of shapes including Delaunay meshes, iso-surfaces, point clouds, ‘knotted' surfaces, surfaces with boundaries and even non-manifolds. We later upgrade this algorithm based on some key observations. These modifications reduce the running time of the algorithm dramatically without sacrificing loop qualities. Given a surface M, a cut locus with respect to a point p in M is the set of points in M that have more than one equal shortest geodesic path from p. A cut locus contains most of the topological information of a sur (open full item for complete abstract)

Committee: Tamal Dey PhD (Advisor); Yusu Wang PhD (Committee Member); Rephael Wenger PhD (Committee Member) Subjects: Computer Science