CMU-CS-11-121Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-11-121
Donald R. Sheehy July 2011 Ph.D. Thesis
Keywords: Computational Goemetry, Mesh Generation, Persistent Homology
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 This page maintained by reports@cs.cmu.edu |