2018/08/20 by Asai, Ryo, Shah, Jay
#55U10 #Algebraic Topology (math.AT) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.06568
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 π of the poset P of simplices of a simplicial complex K, such that for each strata Pπ=i ⊂ P, Pπ=i is maximal among all open subposets U ⊂ Pπ=i in its closure such that the restriction of the local ℤ-homology sheaf of Pπ=i to U is locally constant. Passage to the localization of P dictated by π then attaches a canonical stratified homotopy type to K. Using ∞-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 ≤ 3, and show that it runs in polynomial time. In particular, an n-dimensional simplicial complex with size s and n≤3 can be processed in O(s2) 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.