In topology, the VietorisâÂÂRips complex, also called the Vietoris complex or Rips complex, is a way of forming a topological space from distances in a set of points. It is an abstract simplicial complex that can be defined from any metric space M and distance ô by forming a simplex for every finite set of points that has diameter no more than ô. That is, it is a family of finite subsets of M, in which we think of a subset of k points as forming a (k − 1)-dimensional simplex (an edge for two points, a triangle for three points, a tetrahedron for four points, etc.); if a finite set S has the property that the distance between every pair of points in S is at most ô, then we include S as a simplex in the complex.
The VietorisâÂÂRips complex was originally called the Vietoris complex, for Leopold Vietoris, who introduced it as a means of extending homology theory from simplicial complexes to metric spaces. After Eliyahu Rips applied the same complex to the study of hyperbolic groups, its use was popularized by , who called it the Rips complex. The name "VietorisâÂÂRips complex" is due to .
The VietorisâÂÂRips complex is closely related to the ÃÂech complex (or nerve) of a set of balls, which has a simplex for every finite subset of balls with nonempty intersection. In a geodesically convex space Y, the VietorisâÂÂRips complex of any subspace X â Y for distance ô has the same points and edges as the ÃÂech complex of the set of balls of radius ô/2 in Y that are centered at the points of X. However, unlike the ÃÂech complex, the VietorisâÂÂRips complex of X depends only on the intrinsic geometry of X, and not on any embedding of X into some larger space.
As an example, consider the uniform metric space M<sub>3</sub> consisting of three points, each at unit distance from each other. The VietorisâÂÂRips complex of M<sub>3</sub>, for ô = 1, includes a simplex for every subset of points in M<sub>3</sub>, including a triangle for M<sub>3</sub> itself. If we embed M<sub>3</sub> as an equilateral triangle in the Euclidean plane, then the ÃÂech complex of the radius-1/2 balls centered at the points of M<sub>3</sub> would contain all other simplexes of the VietorisâÂÂRips complex but would not contain this triangle, as there is no point of the plane contained in all three balls. However, if M<sub>3</sub> is instead embedded into a metric space that contains a fourth point at distance 1/2 from each of the three points of M<sub>3</sub>, the ÃÂech complex of the radius-1/2 balls in this space would contain the triangle. Thus, the ÃÂech complex of fixed-radius balls centered at M<sub>3</sub> differs depending on which larger space M<sub>3</sub> might be embedded into, while the VietorisâÂÂRips complex remains unchanged.
If any metric space X is embedded in an injective metric space Y, the VietorisâÂÂRips complex for distance ô and X coincides with the ÃÂech complex of the balls of radius ô/2 centered at the points of X in Y. Thus, the VietorisâÂÂRips complex of any metric space M equals the ÃÂech complex of a system of balls in the tight span of M.
Equipped with the word metric relative to a generating set, a finitely generated group G is a metric space. The associated Vietoris-Rips complex is a finite-dimensional locally finite simplicial complex on which G acts geometrically, i.e. properly discontinuously and with compact quotient. This action is faithful, with finite stabilizers. Moreover, if G is torsion-free, the action if free.
When G is hyperbolic, for ô large enough the associated Vietoris-Rips complex is contractible. This implies that the group is of type F<sub>âÂÂ</sub>, is finitely presented and of finite cohomological dimension.
The VietorisâÂÂRips complex for ô = 1 contains an edge for every pair of points that are at unit distance or less in the given metric space. As such, its 1-skeleton is the unit disk graph of its points. It contains a simplex for every clique in the unit disk graph, so it is the clique complex or flag complex of the unit disk graph. More generally, the clique complex of any graph G is a VietorisâÂÂRips complex for the metric space having as points the vertices of G and having as its distances the lengths of the shortest paths in G.
If M is a closed Riemannian manifold, then for sufficiently small values of ô the VietorisâÂÂRips complex of M, or of spaces sufficiently close to M, is homotopy equivalent to M itself.
describe efficient algorithms for determining whether a given cycle is contractible in the Rips complex of any finite point set in the Euclidean plane.
As with unit disk graphs, the VietorisâÂÂRips complex has been applied in computer science to model the topology of ad hoc wireless communication networks. One advantage of the VietorisâÂÂRips complex in this application is that it can be determined only from the distances between the communication nodes, without having to infer their exact physical locations. A disadvantage is that, unlike the ÃÂech complex, the VietorisâÂÂRips complex does not directly provide information about gaps in communication coverage, but this flaw can be ameliorated by sandwiching the ÃÂech complex between two VietorisâÂÂRips complexes for different values of ô. An implementation of VietorisâÂÂRips complexes can be found in the TDAstats R package.
VietorisâÂÂRips complexes have also been applied for feature-extraction in digital image data; in this application, the complex is built from a high-dimensional metric space in which the points represent low-level image features.
The collection of all VietorisâÂÂRips complexes is a commonly applied construction in persistent homology and topological data analysis, and is known as the Rips filtration.