In
topological data analysis, a subdivision bifiltration is a collection of
filteredsimplicial complexes, typically built upon a set of data points in a
metric space, that captures shape and density information about the underlying data set. The subdivision bifiltration relies on a natural filtration of the
barycentric subdivision of a
simplicial complex by
flags of minimum dimension, which encodes density information about the metric space upon which the complex is built. The subdivision bifiltration was first introduced by Donald Sheehy in 2011 as part of his doctoral thesis[1] (later subsumed by a conference paper in 2012[2]) as a
discrete model of the
multicover bifiltration, a continuous construction whose underlying framework dates back to the 1970s.[3] In particular, Sheehy applied the construction to both the
Vietoris-Rips and
Čech filtrations, two common objects in the field of topological data analysis.[4][5][6] Whereas single parameter filtrations are not robust with respect to outliers in the data,[7] the subdivision-Rips and -Cech bifiltrations satisfy several desirable stability properties.[8]
There is a natural
filtration on by considering for each
natural number the maximal subcomplex of spanned by
vertices of corresponding to simplices of of dimension at least , which is denoted . In particular, by this convention, then . Considering the sequence of nested subcomplexes given by varying the parameter , we obtain a filtration on known as the subdivision filtration. Since the complexes in the subdivision filtration shrink as increases, we can regard it as a
functor from the
oppositeposetal category to the category of simplicial complexes and
simplicial maps.
Let be a
partially ordered set. Given a simplicial filtration , regarded as a functor from the posetal category of to the category , by applying the subdivision filtration object-wise on , we obtain a two-parameter filtration , called the subdivision bifiltration.[10]
In particular, when we take to be the
Rips or
Čech filtration, we obtain bifiltrations and , respectively.
Properties
The subdivision-Čech bifiltration is weakly equivalent to the multicover bifiltration, implying that they have isomorphic persistent homology. A combinatorial proof of this statement was given in Sheehy's original conference paper, but a more algebraic version was presented in 2017 by Cavanna et al.[11] The ideas from Cavanna's proof were later generalized by Blumberg and Lesnick in a 2022 paper on 2-parameter persistent homology.[8]
By the size of a bifiltration, we mean the number of simplices in the largest complex. The subdivision-Čech bifiltration has exponential size as a function of the number of vertices.[12] This implies that its
homology cannot be directly computed in
polynomial time. However, for points in Euclidean space, the homology of subdivision-Čech can be computed in polynomial time, up to
weak equivalence, via a construction known as the rhomboid bifiltration. As a precursor to the rhomboid bifiltration,
Edelsbrunner and Osang presented in 2021 a
polyhedralcell complex called the rhomboid tiling, which they used to compute horizontal or vertices slices of the multicover bifiltration up to weak equivalence.[13] This was extended a year later by Corbet et al. to the rhomboid bifiltration, which is weakly equivalent to the multicover bifiltration, but has polynomial size.[12]
^Cavanna, Nicholas J.; Gardner, Kirk P.; Sheehy, Donald R. (2017). "When and Why the Topological Coverage Criterion Works". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2679–2690.
doi:
10.1137/1.9781611974782.177.
ISBN978-1-61197-478-2.