Given a real-valued function f defined over a manifold M embedded in R^d, we are interested in recovering structural information about f from the sole information of its values on a finite sample P. Existing methods provide approximation to the persistence diagram of f when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.

Algorithms for persistent homology are well-studied where homomorphisms are induced by inclusion maps. In this paper, we propose a practical algorithm for computing persistence under Z2 coefficients for a (monotone) sequence of general simplicial maps and show how these maps arise naturally in some applications of topological data analysis.

The efficiency of extracting topological information from point data depends largely on the complex that is built on top of the data points. From a computational viewpoint, the most favored complexes for this purpose have so far been Vietoris-Rips and witness complexes. While the ietoris-Rips complex is simple to compute and is a good vehicle for extracting topology of sampled spaces, its size is huge--particularly in high dimensions. The witness complex on the other hand enjoys a smaller size because of a subsampling, but fails to capture the topology in high dimensions unless imposed with extra structures. We investigate a complex called the graph induced complex that, to some extent, enjoys the advantages of both. It works on a subsample but still retains the power of capturing the topology as the Vietoris-Rips complex. It only needs a graph connecting the original sample points from which it builds a complex on the subsample thus taming the size considerably. We show that, using the graph induced complex one can (i) infer the one-dimensional homology of a manifold from a very lean subsample, (ii) reconstruct a surface in three dimension from a sparse subsample without computing Delaunay triangulations, (iii) infer the persistent homology groups of compact sets from a sufficiently dense sample. We provide experimental evidences in support of our theory.

A special family of non-trivial loops on a surface called handle and tunnel loops associates closely to geometric features of "handles" and "tunnels" respectively in a 3D model. The identification of these handle and tunnel loops can benefit a broad range of applications from topology simplification/repair, and surface parameterization, to feature and shape recognition. Many of the existing efficient algorithms for computing non-trivial loops cannot be used to compute these special type of loops. The two algorithms known for computing handle and tunnel loops provably have a serious drawback that they both require a tessellation of the interior and exterior spaces bounded by the surface. Computing such a tessellation of three dimensional space around the surface is a non-trivial task and can be quite expensive. Furthermore, such a tessellation may need to refine the surface mesh, thus causing the undesirable side-effect of outputting the loops on an altered surface mesh. In this paper, we present an efficient algorithm to compute a basis for handle and tunnel loops without requiring any 3D tessellation. This saves time considerably for large meshes making the algorithm scalable while computing the loops on the original input mesh and not on some refined version of it. We use the concept of the Reeb graph which together with several key theoretical insights on linking number provide an initial set of loops that provably constitute a handle and a tunnel basis. We further develop a novel strategy to tighten these handle and tunnel basis loops to make them geometrically relevant. We demonstrate the efficiency and effectiveness of our algorithm as well as show its robustness against noise, and other anomalies in the input.

An elegant and efficient mesh clustering algorithm is presented. The faces of a polygonal mesh are divided into different clusters for mesh coarsening purpose by approximating the Centroidal Voronoi Tessellation of the mesh. The mesh coarsening process after clustering can be done in an isotropic or anisotropic fashion. The presented algorithm improves previous techniques in local geometric operations and parallel updates. The new algorithm is very simple but is guaranteed to converge, and generates better approximating meshes with the same computation cost. Moreover, the new algorithm is suitable for the variational shape approximation problem with L2, 1 distortion error metric and the convergence is guaranteed. Examples demonstrating efficiency of the new algorithm are also included in the paper.