The Definition of Chech Complexes
Definition 1 2
Given a metric space $\left( X, d \right)$ and a positive number $\varepsilon > 0$, for a finite set $S \subset X$, the abstract simplicial complex $\check{C}_{\varepsilon} (S)$ defined as follows is called a Čech Complex. $$ \check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\} $$
Here, $B_{d} (c; r)$ is an open ball in the given metric space with centre $c \in X$ and radius $r \in \mathbb{R}$. $$ B_{d} \left( c ; r \right) := \left\{ x \in X : d (c,x) < r \right\} $$
Explanation
Although the definition might be a bit too technically written, it is easier to simply think of it as a simplicial complex that recognizes simplices only when the balls overlap in Euclidean space $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$. Instead of just focusing on formulas, one can understand it immediately by checking what differs from the Vietoris-Rips Complex.
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 image compares the Vietoris-Rips Complex and the Čech Complex using the same data. The top is $\text{VR}_{\varepsilon}$, and the bottom is $\check{C}_{\varepsilon}$.
- Vietoris-Rips requires the existence of a $k-1$-simplex as a face for including a $k$-simplex. In the example, since the $1$-simplices $AB$, $BC$, and $CA$ exist, the $2$-simplex $ABC$ is included.
- In contrast, the Čech Complex requires not only the inclusion of its faces but also that the $ABC$ itself be tied together at a single point. This indicates that constructing a Čech Complex is more demanding than constructing a Vietoris-Rips Complex, leading to the following understanding: $$ \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} $$
One can infer that the Čech Complex might contain slightly more information than the Vietoris-Rips Complex through its definition. $\text{VR}_{\varepsilon}$ states that as long as the given $k \le n$ points are connected, it unequivocally confirms the existence of a $k-1$-simplex. This implies no difference between the mere existence of a simplex and the existence of all its faces. For example, saying that a $2$-simplex $ABC$ exists or that $1$-simplices $AB$, $BC$, and $CA$ exist is precisely equivalent; knowing one almost renders the other redundant. In contrast, $\check{C}_{\varepsilon}$ cannot assure the existence of $ABC$ based solely on the existence of $AB$, $BC$, and $CA$ and requires separate verification. From this perspective, the Čech Complex can be seen as providing a more detailed view of the data compared to the Vietoris-Rips Complex.
On the other hand, from the aspect of actual computation, constructing a Vietoris-Rips Complex is overwhelmingly cheaper. This contrasts with $\text{VR}_{\varepsilon}$, where merely calculating the distance between fixed points is simple, versus $\check{C}_{\varepsilon}$, where it is unknown where the balls of points meet, and even if they do meet, it is unclear whether it is longer or shorter than $\varepsilon$. One of the methods to overcome this and construct a Čech Complex is considering finding the minimum enclosing disk, for example, through Welzl’s Algorithm, but each calculation is quite expensive, and this costly computation needs to be repeated for all possible combinations of points.