Definition of Vietoris-Rips Complex
Definition 1 2
Simple Definition
Let us assume a Euclidean space $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$ and a positive number $\varepsilon > 0$ are given. For a finite set $S \subset \mathbb{R}^{d}$, a simplicial complex $\text{VR}_{\varepsilon} (S)$ that satisfies the following two conditions is called a Vietoris-Rips Complex.
- (i): It has $S$ as the set of vertices.
- (ii): A simplex $\left[ v_{0} , v_{1} , \cdots, v_{k} \right]$ in $\text{VR}_{\varepsilon} (S)$ belongs to $\text{VR}_{\varepsilon} (S)$ if and only if for all $0 \le i,j \le k$, the following holds true. $$ \left\| v_{i} - v_{j} \right\|_{2} \le 2 \varepsilon $$
Complex Definition
Given a metric space $\left( X, d \right)$ and a positive number $\varepsilon > 0$, an abstract simplicial complex $\text{VR}_{\varepsilon} (S)$ defined as follows is called a Vietoris-Rips Complex. $$ \text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\} $$ Here, $\diam$ denotes the Diameter, which is defined as the supremum of the distances between all points of the given set $\sigma \subset X$. $$ \diam \sigma := \sup_{x_{1} , x_{2} \in \sigma} d \left( x_{1} , x_{2} \right) $$
Explanation
The Vietoris-Rips Complex, also commonly shortened to VR Complex or Rips Complex, can essentially be understood through its definition. Whether through the simple or complex definition, the core principle that defines a simplex’s eligibility is that all the distances between points included must be less than or equal to $2 \varepsilon$. Visualizing this concept, one can think of vertices that are $0$-simplices at the center, with spheres of radius $\varepsilon$. Then, based on these spheres touching one another, a $1$-simplex is formed if two vertices are connected in a $1$-simplex and further creating a $2$-simplex if three vertices connect within a $1$-simplex, which is how a VR Complex can be built.
Difference Between Vietoris-Rips Complex and Čech Complex
Vietoris-Rips Complex: $$\text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\}$$
Čech Complex: $$\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}$$
The following images compare the same dataset for the Vietoris-Rips Complex and the Čech Complex. The top is for $\text{VR}_{\varepsilon}$, and the bottom is for $\check{C}_{\varepsilon}$.
- The Vietoris-Rips requires only the existence of a $k-1$-simplex as its face for including a $k$-simplex. In the example, since $1$-simplices $AB$, $BC$, and $CA$ exist, the $2$-simplex $ABC$ is included.
- On the contrary, the Čech Complex requires not only the inclusion of these faces but also that the $ABC$ itself is formed by the spheres intersecting at a single point. This means that constructing a Čech Complex is more stringent than constructing a Vietoris-Rips Complex, thereby leading to the following observation. $$ \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} $$ Furthermore, the following fact is known. $$ \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} \subset \check{C}_{2 \varepsilon} $$
We can infer that perhaps the Čech Complex can contain a bit more information than the Vietoris-Rips Complex. $\text{VR}_{\varepsilon}$ states that as long as the given points are connected, the existence of a $k-1$-simplex is automatically confirmed. Essentially, there’s no difference between the existence of a simplex and all its faces; knowing one practically renders the other information redundant. Conversely, $\check{C}_{\varepsilon}$ cannot assure the existence of $ABC$ solely based on the existence of $AB$, $BC$, and $CA$, necessitating an additional verification. It can thus be expected that the Čech Complex examines data details more intricately than the Vietoris-Rips Complex.
However, from the perspective of actual computation, constructing a Vietoris-Rips Complex is significantly cost-effective. Indeed, unlike $\text{VR}_{\varepsilon}$, which simply calculates the distance between fixed points, $\check{C}_{\varepsilon}$ not only lacks information on where the spheres intersect but also cannot determine if their intersection is shorter or longer than $\varepsilon$. Overcoming this and constructing a Čech Complex might involve finding the smallest enclosing disk using techniques such as the Welzl’s algorithm, but each calculation is relatively expensive and must be repeated for all possible combinations of points.