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

Scalar functions are virtually ubiquitous in scientific research. A vast amount of research has been conducted in visualization and exploration of low-dimensional data during the last few decades, but adapting these techniques to high-dimensional, topologically-complex data remains challenging. Traditional metric-preserving dimensionality reduction techniques suffer when the intrinsic dimension of data is high, as the metric cannot generally survive projection into low dimensions. The metric distortion can be arbitrarily large, and preservation of topological structure is not guaranteed, resulting in a misleading view of the data. When preservation of geometry is not possible, topological analysis provides a promising alternative. As an example, simplicial homology characterizes the structure of a topological space (i.e. a simplicial complex) via its intrinsic topological features of various dimensions. Unfortunately, this information can be abstract and difficult to comprehend. The ranks of these homology groups (the Betti numbers) offer a simpler, albeit coarse, interpretation as the number of voids of each dimension. In high dimensions, these approaches suffer from exponential time complexity, which can render them impractical for use with real data. In light of these difficulties, we turn to an alternative type of topological characterization. We investigate the Reeb graph as a visualization and analysis tool for such complex data. The Reeb graph captures the topology of the set of level sets of a scalar function, providing a simple, intuitive, and informative topological representation. We present the first sub-quadratic expected time algorithm for computing the Reeb graph of an arbitrary simplicial complex, opening up the possibility of using the Reeb graph as a tool for understanding high-dimensional data. While the Reeb graph effectively captures some topological structure, it is still somewhat terse. The Morse-Smale complex summarizes a scalar function by b (open full item for complete abstract)

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

Master of Science, Miami University, 2020, Mathematics

This thesis is to provide an overview of Topological Data Analysis (TDA) for the advanced undergraduate or early graduate student. This thesis assumes familiarity with basic graph theory, point-set topology, and introductory algebraic topology. Furthermore, this thesis will study phylogenetic relationship of NA gene in various Influenza A strains and determine if horizontal evolution has occurred with the strains under consideration. Furthermore, this thesis serves as a verification to the results published in a paper in 2013, in which, TDA was used to study influenza A HA and NA.

Committee: Daniel Farley PhD (Advisor); Paul Larson PhD (Committee Member); Ivonne Ortiz PhD (Committee Member) Subjects: Bioinformatics; Biology; Genetics; Mathematics; Virology

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

Topological Data Analysis is a rapidly growing field to extract and analyze useful topological features from especially difficult datasets. Topological features, with their wide application, provide us a richer and more robust view of shapes compared to geometric features. During recent decades, the problem of computing the topological entities of a space has drawn much attention. In this thesis, I present my focused research on two topological entities: minimal homology basis of simplicial complexes and persistent homology of directed graphs. In the first part of this thesis, we focus on efficient computation of shortest cycles which form a homology basis under $\mathbb{Z}_2$-additions in a given simplicial complex $\mathcal{K}$. This problem has been researched actively in recent years. The complexity of these algorithms depends on the rank $g$ of the one-dimensional homology group of $\mathcal{K}$. This rank $g$ has a lower bound of $\Theta(n)$, where $n$ denotes the number of simplices in $\mathcal{K}$. When $g=\Theta(n)$, the current best algorithm, as far as we know, gives an $O(n^{\omega+1})$ worst-case time complexity where $\omega<2.373$ is the fast matrix multiplication exponent. In this work, we improved this time complexity. Combining the idea of annotations from \cite{annotation} and the divide and conquer technique from \cite{DivideConquer}, we present an algorithm that runs in $O(n^\omega+n^2g)$ time giving the first $O(n^3)$ worst-case algorithm for general complexes. If instead of minimal basis, we settle for approximate basis, we can improve the running time even further. We show that a $2$-approximation to the minimal basis can be computed in $O(n^{\omega}\sqrt{n\log n})$ worst-case time. We also study more general measures for defining the minimal basis and identify reasonable conditions on these measures that allow computing a minimal basis efficiently. We extend our approach to higher dimensional cycles where we improve the running time fo (open full item for complete abstract)

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

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, Mathematics

This project introduces a flexible mathematical model used to represent problems of separating objects in space. Specifically, the notion of disentangling objects is formalized, and the definitions of this model are adapted from several used in the study of topology. Since spatial separation problems have been studied using computational models, methods were considered for translating problems from the mathematical model to that of computation. Upon acknowledging the assumptions made between the models, there is a review of computational complexity results for both determining the ability to disentangle objects and finding the fastest untangling motion.

Committee: Sergei Chmutov PhD (Advisor); Jenny Sheldon PhD (Advisor); Thomas Kerler PhD (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, Computer Science and Engineering

In scientific research and industrial applications, the questions of computing, characterizing and tracking important features in the input data arise with noticeable frequency. Feature detection is a critical step in automated data processing such as mesh generation. In high-dimensional data analysis, there is a strong demand for feature classification and tracking methods. Finally, in scientific visualization and simulation of real-world phenomena, modeling small-scale features is often essential for visual realism. All these questions motivated a substantial amount of research in geometric modeling, computational geometry, computational topology and computer animation. The first topic we investigate in regard to these questions is feature processing for automated mesh generation. Specifically, for a shape provided as a collection of possibly improperly meeting and/or self-intersecting patches, we construct a watertight mesh that has many of these representation errors fixed. To achieve that, we augment the existing Delaunay meshing algorithm for piecewise smooth domains with a preprocessing step that recomputes the 1-skeleton of the complex, producing a valid input for the mesher. For shapes provided in the form of a point cloud data, researchers are often interested in analyzing high-level features, which are traditionally computed using topological methods from simplicial complexes built on top of the point clouds. This motivates the second topic of our research: geometrical and topological queries on arbitrary simplicial complexes. The first problem we tackle is maintaining geometry-aware homological features under changes in the underlying simplicial complex. We capitalize on the theory of persistent homology, which provides a principled way to describe features. Building upon the existing matrix framework, we propose a method for tracking a chosen generator so that it undergoes only local changes. Another question we address is speeding up miscellaneous quer (open full item for complete abstract)

Committee: Tamal K. Dey PhD (Advisor); Huamin Wang PhD (Committee Member); Rephael S. Wenger PhD (Committee Member); William C. Ray PhD (Committee Member) Subjects: Computer Science

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

Recent years have witnessed an unprecedented growth in the generation and availability of large scale and complex data. Such growth has fostered the development of new qualitative methods of data analysis. Among the most prominent are the set of methods falling under the rubric of topological methods. From their inception, topological methods have been gaining in prominence mainly in the studies of scalar data, in particular the topology of scalar functions over manifolds. With the increasing complexity of the available data, there is an interest in extending the topological methods to deal with more complex types of data such as multiple scalar fields and vector fields over manifolds, scalar data over point clouds, as well as scalar fields over high dimensional stratified spaces. In this dissertation we study the extension of topological methods to the treatment of multiple scalar fields, and scalar fields over a variety of domains ranging from the planar to the stratified. We first showcase the use of scalar field topological methods to study 2D vector fields over planar domains. We achieve this by transforming the vector field into multiple scalar fields through the use of Hodge decomposition. Hodge decomposition in 2D allows us to transform the vector field into two scalar fields where we can apply scalar field based topological methods. We take advantage of this decomposition to generate topologically-aware visualization of the vector field. A particular case of multiple scalar functions is a time varying function, where time is treated as a second scalar function. We study two topological constructs in the context of time varying functions: persistent homology and contour trees. We present an algorithm to incrementally update the persistence pairing of a time-varying function defined on a triangular mesh in O(log n), and contour trees of time-varying functions in O(log n + | lnk(p) ∩ lnk(q) |) where |lnk(p)| is the size of the link of a vertex p in the t (open full item for complete abstract)

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

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