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