Algorithmic canonical stratifications of simplicial complexes

Abstract

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}$ is maximal among all open subposets $U\subset \overline{P_{\pi =i}}$ in its closure such that the restriction of the local $\mathbb{Z}$-homology sheaf of $\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 $\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.

36 pages. v3: added reference to Aoki's work on hypercomplete sheaves, otherwise minor changes in response to referee report