Algorithmic canonical stratifications of simplicial complexes

We introduce a new algorithm for the structural analysis of finite abstract simplicial complexes based on local homology. Through an iterative and top-down procedure, our algorithm computes a stratification $\pi$ of the poset $P$ of simplices of a simplicial complex $K$, such that for each strata $P_{\pi=i} \subset P$,$P_{\pi=i}$ismaximalamongallopensubposets$U \subset \overline{P_{\pi=i}}$initsclosuresuchthattherestrictionofthelocal$$\mathbb{Z}$$-homologysheafof$\overline{P_{\pi=i}}$to$U$ is locally constant. Passage to the localization of $P$ dictated by $\pi$ then attaches a canonical stratified homotopy type to $K$. Using $\mathrm{\infty }$-categorical methods, we first prove that the proposed algorithm correctly computes the canonical stratification of a simplicial complex; along the way, we prove a few general results about sheaves on posets and the homotopy types of links that may be of independent interest. We then present a pseudocode implementation of the algorithm, with special focus given to the case of dimension $\le 3$, and show that it runs in polynomial time. In particular, an $n$-dimensional simplicial complex with size $s$ and $n\le 3$ can be processed in O($s^2$) time or O($s$) given one further assumption on the structure. Processing Delaunay triangulations of $2$-spheres and $3$-balls provides experimental confirmation of this linear running time.