Topological Inference via Meshing

SOCG: ACM Symposium on Computational Geometry
2010

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 $R^d$.
Classical approaches rely on the Cech, Rips, $\alpha$-complex, or
witness complex filtrations of $P$, whose complexities scale
badly with $d$. For instance, the $\alpha$-complex filtration incurs
the $n^{\Omega(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(d^2)}n$. A nice property of these
filtrations is to be interleaved multiplicatively with the family of
offsets of $P$, so that the persistence diagram of $P$ can be
approximated in $2^{O(d^2)}n^3$ time in theory, with a near-linear
observed running time in practice.
Thus, our approach remains tractable in medium dimensions, say 4 to 10.

@inproceedings{hudson10topological, Title = {Topological Inference via Meshing}, Author = {Beno\^{i}t Hudson and Steve Y. Oudot and Gary L. Miller and Donald R. Sheehy}, Booktitle = {SOCG: Proceedings of the 26th ACM Symposium on Computational Geometry}, Year = {2010}}