  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 a
significant reduction in the number of comparisons required to construct the
Vietoris-Rips compared to state-of-the-art algorithms, which is seen here by
examining the computational complexity of the critical step in the algorithms.
In experiments comparing a C/C++ implementation of our algorithm to the GUDHI
v3.9.0 software package, this results in an observed $5$-$10$-fold improvement
in speed of on sufficiently sparse Erd\H{o}s-R\'enyi graphs with the best
advantages as the graphs become sparser, as well as for higher dimensional
Vietoris-Rips complexes. We further clarify that the algorithm described in
Boissonnat and Maria (https://doi.org/10.1007/978-3-642-33090-2_63) for the
construction of the Vietoris-Rips complex is exactly the Incremental Algorithm
from Zomorodian (https://doi.org/10.1016/j.cag.2010.03.007), albeit with the
additional requirement that the result be stored in a tree structure, and we
explain how these techniques are different from the algorithm presented here.
