Mesh Enhanced Persistent Homology

We apply ideas from mesh generation to improve the time and space complexity of computing the persistent homology of a point set in R^d. The traditional approach to persistence starts with the -complex of the point set and thus incurs the O(n^⌊d/2⌋) size of the Delaunay triangulation. The common alternative is to use a Rips complex and then to truncate the filtration when the size of the complex becomes prohibitive, possibly before discovering relevant topological features. Given a point set P of n points in R^d, we construct a new filtration, the -mesh, of size O(n) in time O(n²) with persistent homology approximately the same as that of the -shape filtration. This makes it possible to compute the complete persistence barcode in O(n³) time, where n is the number of points. Previously, this bound was only achievable (with exponentially worse constants) for computing partial barcodes from uniform samples from manifolds. The constants in this paper are all singly exponential in d, making them suitable for medium dimensions.