Vietoris–Rips complex
Encyclopedia
In topology
, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, 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
at most δ. 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.
, 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 group
s, its use was popularized by , who called it the Rips complex. The name "Vietoris–Rips complex" is due to .
(or nerve) of a set of ball
s, 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 M3 consisting of three points, each at unit distance from each other. The Vietoris–Rips complex of M3, for δ = 1, includes a simplex for every subset of points in M3, including a triangle for M3 itself. If we embed M3 as an equilateral triangle in the Euclidean plane, then the Čech complex of the radius-1/2 balls centered at the points of M3 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 M3 is instead embedded into a metric space that contains a fourth point at distance 1/2 from each of the three points of M3, 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 M3 differs depending on which larger space M3 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.
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.
, 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.
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 δ.
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.
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is an abstract simplicial complex
Abstract simplicial complex
In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets...
that can be defined from any metric space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
M and distance δ by forming a simplex
Simplex
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,...
for every finite set of points that has diameter
Diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...
at most δ. 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.
History
The Vietoris–Rips complex was originally called the Vietoris complex, for Leopold VietorisLeopold Vietoris
Leopold Vietoris was an Austrian mathematician and a World War I veteran who gained additional fame by becoming a supercentenarian...
, who introduced it as a means of extending homology theory
Homology (mathematics)
In mathematics , homology is a certain general procedure to associate a sequence of abelian groups or modules with a given mathematical object such as a topological space or a group...
from simplicial complexes to metric spaces. After Eliyahu Rips
Eliyahu Rips
Eliyahu Rips, also Ilya Rips is a Latvian-born Israeli mathematician known for his research in geometric group theory. He became known to the general public following his coauthoring a paper on the Torah Code....
applied the same complex to the study of hyperbolic group
Hyperbolic group
In group theory, a hyperbolic group, also known as a word hyperbolic group, Gromov hyperbolic group, negatively curved group is a finitely generated group equipped with a word metric satisfying certain properties characteristic of hyperbolic geometry. The notion of a hyperbolic group was introduced...
s, its use was popularized by , who called it the Rips complex. The name "Vietoris–Rips complex" is due to .
Relation to Čech complex
The Vietoris–Rips complex is closely related to the Čech complexCech cohomology
In mathematics, specifically algebraic topology, Čech cohomology is a cohomology theory based on the intersection properties of open covers of a topological space. It is named for the mathematician Eduard Čech.-Motivation:...
(or nerve) of a set of ball
Ball (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
s, which has a simplex for every finite subset of balls with nonempty intersection: in a geodesically convex space
Geodesic convexity
In mathematics — specifically, in Riemannian geometry — geodesic convexity is a natural generalization of convexity for sets and functions to Riemannian manifolds...
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 M3 consisting of three points, each at unit distance from each other. The Vietoris–Rips complex of M3, for δ = 1, includes a simplex for every subset of points in M3, including a triangle for M3 itself. If we embed M3 as an equilateral triangle in the Euclidean plane, then the Čech complex of the radius-1/2 balls centered at the points of M3 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 M3 is instead embedded into a metric space that contains a fourth point at distance 1/2 from each of the three points of M3, 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 M3 differs depending on which larger space M3 might be embedded into, while the Vietoris–Rips complex remains unchanged.
If any metric space X is embedded in an injective metric space
Injective metric space
In metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a metric space with certain properties generalizing those of the real line and of L∞ distances in higher-dimensional vector spaces...
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
Tight span
In metric geometry, the metric envelope or tight span of a metric space M is an injective metric space into which M can be embedded. In some sense it consists of all points "between" the points of M, analogous to the convex hull of a point set in a Euclidean space. The tight span is also sometimes...
of M.
Relation to unit disk graphs and clique complexes
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 graphUnit disk graph
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other....
of its points. It contains a simplex for every clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
in the unit disk graph, so it is the clique complex
Clique complex
Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.-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
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
of G and having as its distances the lengths of the shortest paths in G.
Other results
If M is a closed Riemannian manifoldRiemannian manifold
In Riemannian geometry and the differential geometry of surfaces, a Riemannian manifold or Riemannian space is a real differentiable manifold M in which each tangent space is equipped with an inner product g, a Riemannian metric, which varies smoothly from point to point...
, then for sufficiently small values of δ the Vietoris–Rips complex of M, or of spaces sufficiently close to M, is homotopy equivalent
Homotopy
In topology, two continuous functions from one topological space to another are called homotopic if one can be "continuously deformed" into the other, such a deformation being called a homotopy between the two functions...
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.
Applications
As with unit disk graphs, the Vietoris–Rips complex has been applied in computer scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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 δ.
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.