A New Construction of the Vietoris-Rips Complex

We present a new, inductive construction of the Vietoris-Rips complex, in which we take advantage of a small amount of unexploited combinatorial structure in the $k$-skeleton of the complex in order to avoid unnecessary comparisons when identifying its $(k+1)$-simplices. In doing so, we achieve an order-of-magnitude speedup over current algorithms when constructing the clique complexes of Erd\H{o}s-R\'enyi graphs.