Donald R. Sheehy Mesh Generation and Geometric Persistent Homology Degree Type: Ph.D. in Computer Science Advisor(s): Gary Miller Graduated: August 2011 Abstract: 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. Thesis Committee: Gary L. Miller (Chair) Guy Blelloch Daniel D.K. Sleator Afra J. Zomorodian (Dartmouth College) Jeannette Wing, Head, Computer Science Department Randy Bryant, Dean, School of Computer Science Keywords: Computational Goemetry, Mesh Generation, Persistent Homology CMU-CS-11-121.pdf (2.33 MB) ( 147 pages) Copyright Notice