Topological inference via meshing

We apply ideas from mesh generation to improve the time and space complexities of computing the full persistent homological information associated with a point cloud P in Euclidean space ℝ^d. Classical approaches rely on the Čech, Rips, α-complex, or witness complex filtrations of P, whose complexities scale up very badly with d. For instance, the α-complex filtration incurs the n^Ω(d) size of the Delaunay triangulation, where n is the size of P. The common alternative is to truncate the filtrations when the sizes of the complexes become prohibitive, possibly before discovering the most relevant topological features. In this paper we propose a new collection of filtrations, based on the Delaunay triangulation of a carefully-chosen superset of P, whose sizes are reduced to 2^O(d2)n. Our filtrations interleave multiplicatively with the family of offsets of P, so that the persistence diagram of P can be approximated in 2^O(d2)n³ time in theory, with a near-linear observed running time in practice. Thus, our approach remains tractable in medium dimensions, say 4 to 10.