Mesh generation is a tool for discretizing functions by discretizing space. Traditionally, meshes are used in scientific computing for finite element analysis. Algorithmic ideas from mesh generation can also be applied to data analysis.

Data sets often have an intrinsic geometric and topological structure. The goal of many problems in geometric inference is to expose this intrinsic structure. One important structure of a point cloud is its geometric persistent homology, a multiscale description of the topological features of the data with respect to distances in the ambient space.

In this thesis, I bring tools from mesh generation to bear on geometric persistent homology by using a mesh to approximate distance functions induced by a point cloud. Meshes provide an efficient way to compute geometric persistent homology. I present the first time-optimal algorithm for computing quality meshes in any dimension. Then, I show how these meshes can be used to provide a substantial speedup over existing methods for computing the full geometric persistence information for range of distance functions.

147 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu