Browsing by Author "Edelsbrunner, Herbert"

This thesis is concerned with a structure called the Reeb graph. There are three main problems considered. The first is devising an efficient algorithm for comnstructing the Reeb graph of a simplicial complex with respect to a generic simplex-wise linear real-valued function. We present an algorithm that builds the Reeb graph in almost optimal worst-case deterministic time. This was the first deterministic algorithm with the time bound which is linear up to a logarithmic factor. Without loss of generality, the complex is assumed to be 2-dimensional. The algorithm works by sweeping the function values and maintaining a spanning forest for the preimage, or the level-set, of the value. Using the observation that the operations that change the level-sets are off-line, we was able to achieve the above bound.

The second topic is the dynamic Reeb graphs. As the function changes its values, the Reeb graph also changes. We are interested in updating the Reeb graph. We reduce this problem to a graph problem that we call retroactive graph connectivity. We obtain algorithms for dynamic Reeb graphs, by using data structures that solve the graph problem.

The third topic is an argument regarding the complexity of computing Betti numbers. This problem is also related to the Reeb graph by means of the vertical Homology classes. The problem considered here is whether the realization of a simplicial complex in the Euclidean 4-space can result in an algorithm for computing its Homology groups faster than the usual matrix reduction methods. Using the observation that the vertical Betti numbers can always be computed more efficiently using the Reeb graph, we show that the answer to this question is in general negative. For instance, given a square matrix over the field with two elements, we construct a simplicial complex in linear time, realized in euclidean 4-space and a function on it, such that its Horizontal homology group, over the same field, is isomorphic with the null-space of the matrix. It follows that the Betti number computation for complexes realized in the 4-space is as hard as computing the rank for a sparse matrix.

In this thesis we explore and extend the theory of persistent homology, which captures topological features of a function by pairing its critical values. The result is represented by a collection of points in the extended plane called persistence diagram.

We start with the question of ridding the function of topological noise as suggested by its persistence diagram. We give an algorithm for hierarchically finding such epsilon-simplifications on 2-manifolds as well as answer the question of when it is impossible to simplify a function in higher dimensions.

We continue by examining time-varying functions. The original algorithm computes the persistence pairing from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. We describe how to maintain the pairing in linear time per transposition of consecutive simplices. A side effect of the update algorithm is an elementary proof of the stability of persistence diagrams. We introduce a parametrized family of persistence diagrams called persistence vineyards and illustrate the concept with a vineyard describing a folding of a small peptide. We also base a simple algorithm to compute the rank invariant of a collection of functions on the update procedure.

Guided by the desire to reconstruct stratified spaces from noisy samples, we use the vineyard of the distance function restricted to a 1-parameter family of neighborhoods of a point to assess the local homology of a sampled stratified space at that point. We prove the correctness of this assessment under the assumption of a sufficiently dense sample. We also give an algorithm that constructs the vineyard and makes the local assessment in time at most cubic in the size of the Delaunay triangulation of the point sample.

Finally, to refine the measurement of local homology the thesis extends the notion of persistent homology to sequences of kernels, images, and cokernels of maps induced by inclusions in a filtration of pairs of spaces. Specifically, we note that persistence in this context is well defined, we prove that the persistence diagrams are stable, and we explain how to compute them. Additionally, we use image persistence to cope with functions on noisy domains.

This dissertation studiess high dimensional problems from a low dimensional perspective. First, we explore rectifiable curves in high-dimensional space by using the Fréchet distance between and total curvatures of the two curves to bound the difference of their lengths. We create this bound by mapping the curves into R^2 while preserving the length between the curves and increasing neither

the total curvature of the curves nor the Fr\'echet distance between them. The bound is independent of the dimension of the ambient Euclidean space, it improves upon a bound by Cohen-Steiner and Edelsbrunner for dimensions greater than three and it generalizes

a result by F\'ary and Chakerian.

In the second half of the dissertation, we analyze Gaussian mixtures. In particular, we consider the sum of n Gaussians, where each Gaussian is centered at the vertex of a regular n-simplex. Fixing the width of the Guassians and varying the diameter of the simplex from zero to infinity by increasing a parameter that we call the scale factor, we find the window of scale factors for which the Gaussian mixture has more modes, or local maxima, than components of the mixture.

We see that the extra mode created is subtle, but can be higher than the modes closer to the vertices of the simplex. In addition, we prove that all critical points are located on a set of one-dimensional lines (axes) connecting barycenters of complementary faces of

the simplex.

We study how the preimages of a mapping f : X &rarr Y between manifolds vary under perturbations. First, we consider the preimage of a single point and track the history of its connected component as this point varies in Y. This information is compactly represented in a structure that is the generalization of the Reeb graph we call the Reeb space. We study its local and global properties and provide an algorithm for its construction. Using homology, we then consider higher dimensional connectivity of the preimage. We develop a theory quantifying the stability of each homology class under perturbations of the mapping f . This number called robustness is given to each homology class in the preimage. The robustness of a class is the magnitude of the perturbation necessary to remove it from the preimage. The generality of this theory allows for many applications. We apply this theory to quantify the stability of contours, fixed points, periodic orbits, and more.

In this thesis, we explore techniques in statistics and persistent homology, which detect features among data sets such as graphs, triangulations and point cloud. We accompany our theorems with algorithms and experiments, to demonstrate their effectiveness in practice.

We start with the derivation of graph scan statistics, a measure useful to assess the statistical significance of a subgraph in terms of edge density. We cluster graphs into densely-connected subgraphs based on this measure. We give algorithms for finding such clusterings and experiment on real-world data.

We next study statistics on persistence, for piecewise-linear functions defined on the triangulations of topological spaces. We derive persistence pairing probabilities among vertices in the triangulation. We also provide upper bounds for total persistence in expectation.

We continue by examining the elevation function defined on the triangulation of a surface. Its local maxima obtained by persistence pairing are useful in describing features of the triangulations of protein surfaces. We describe an algorithm to compute these local maxima, with a run-time ten-thousand times faster in practice than previous method. We connect such improvement with the total Gaussian curvature of the surfaces.

Finally, we study a stratification learning problem: given a point cloud sampled from a stratified space, which points belong to the same strata, at a given scale level? We assess the local structure of a point in relation to its neighbors using kernel and cokernel persistent homology. We prove the effectiveness of such assessment through several inference theorems, under the assumption of dense sample. The topological inference theorem relates the sample density with the homological feature size. The probabilistic inference theorem provides sample estimates to assess the local structure with confidence. We describe an algorithm that computes the kernel and cokernel persistence diagrams and prove its correctness. We further experiment on simple synthetic data.

We show topological priors play an important role in solving the inverse problem of shape reconstruction. We classify the applications into 1D, 2D, and 3D cases:

In 1D, we show that the persistent extrema of the curvature function of a closed curve are useful for shape simplication. In 2D, we study how to label a scene into multiple tiers to approximate the actual scene layout. We use the number of extrema as a topological prior to bound the complexity of the shape of tiers and study 2D labeling under symmetry shape priors. In 3D, we recover the detailed 3D root shape using multiple 2D images. Three novel ideas are presented. First, we propose the use of harmonic images for background subtraction. Second, we develop the regularized visual hull to preserve the details of an example image in reconstruction. Third, we enforce the topological connectedness by an ecient algorithm that is inspired by the recent development of persistent homology.

Computational efficiency is emphasized throughout the thesis. We show that 1D topological persistence can be computed in O(n) time on a closed curve of n nodes. For 2D tiered labeling, we give an approximation algorithm to compute it in O(nK) time for K tiers on an image of n pixels. For 3D root reconstruction, we accelerate the computation using oct-trees and minimal spanning trees. With these ingredients, it takes only a few seconds to reconstruct a detailed root shape from 40 images of resolution 1600*1200 on a laptop.