In-order Generation of Vietoris-Rips Complexes

The generation of a filtered simplicial complex is a foundational and critical part of the persistent homology pipeline. We will discuss recent work, in collaboration with Ulrich Bauer, on fast generation of Vietoris-Rips complexes. Zomorodian’s algorithm consumes edges in order and builds up all the cofaces at once. Bauer’s groundbreaking software Ripser in turn, enumerates simplices dimension by dimension in a (reverse) lexicographic order, as cofacets of the previous dimension’s simplices, and leaves the sorting to a later stage of the algorithm. As an alternative approach, we propose generating simplices dimension by dimension as cofacets of the previous dimension, but in a way that guarantees simplices appear directly in filtration order.