Vietoris-Rips & Čech Complexes

Learn to construct simplicial complexes from point cloud data using the Vietoris-Rips and Čech constructions.

Building Complexes from Point Clouds

Given a point cloud, how do we construct a simplicial complex that captures its topology? The key insight is to use distance: points that are close together should be connected. The Vietoris-Rips complex is the most computationally tractable way to do this.

For a distance threshold ε (epsilon), the Vietoris-Rips complex VR(ε) includes a simplex [v₀, v₁, ..., vₖ] whenever all pairs of vertices are within distance ε. As ε increases, more simplices appear, and we can track how topological features emerge and disappear.

Interactive Vietoris-Rips Construction

Watch the Vietoris-Rips complex form as you increase ε. Notice how connected components (β₀) merge together, and how loops (β₁) appear and then fill in. Press Play to animate the filtration automatically.

0
Vertices
0
Edges
0
Triangles
0
β₀ (components)
0
β₁ (loops)

The Vietoris-Rips complex connects points within distance ε and fills in all cliques. Watch how topological features (components, loops) appear and disappear as ε increases.

The Vietoris-Rips Complex

VR(P, ε) = { σ = [v₀, ..., vₖ] : d(vᵢ, vⱼ) ≤ ε for all i, j }

In words: a simplex is included if and only if every pair of its vertices is within distance ε. This is equivalent to saying that the simplex is aclique in the graph where vertices are connected if they're within distance ε.

Advantages

  • Only requires pairwise distances
  • Flag complex: determined by 1-skeleton
  • Efficient incremental construction
  • Well-studied theoretical properties

Drawbacks

  • Can be very large (exponential in n)
  • May have spurious high-dimensional simplices
  • Not a nerve of balls (unlike Čech)

Čech vs Vietoris-Rips

The Čech complex Č(ε) includes a simplex [v₀, ..., vₖ] if the balls of radius ε/2 centered at each vertex have a common intersection. This is geometrically natural — it's the nerve of the ball covering — but harder to compute.

Č(P, ε) ⊆ VR(P, ε) ⊆ Č(P, 2ε)
The Vietoris-Rips complex is sandwiched between two Čech complexes

This interleaving theorem guarantees that VR and Čech have similar persistent homology. In practice, we usually compute VR because it only requires pairwise distances (no intersection tests), making it much more efficient.

The VR Filtration

As ε increases from 0 to ∞, we get a nested sequence of complexes:

∅ = VR(0) ⊆ VR(ε₁) ⊆ VR(ε₂) ⊆ ... ⊆ VR(∞)

This nested sequence is called a filtration. Each simplex has abirth time — the smallest ε at which it appears. For the VR complex:

  • Vertices are born at ε = 0 (they're always present)
  • An edge [vᵢ, vⱼ] is born at ε = d(vᵢ, vⱼ)
  • A triangle [vᵢ, vⱼ, vₖ] is born at ε = max(d(vᵢ,vⱼ), d(vᵢ,vₖ), d(vⱼ,vₖ))
  • Higher simplices follow the same pattern: birth = max pairwise distance

Computational Considerations

The VR complex can grow exponentially with the number of points. For n points, the number of k-simplices is bounded by C(n, k+1), which is O(nᵏ⁺¹). In practice, we limit computation to low dimensions (typically k ≤ 2 or 3) and use sparse representations.

O(n²)
Distance matrix
O(n³)
All triangles
O(2ⁿ)
Worst case (all simplices)

Key Takeaways

  • Vietoris-Rips VR(ε) — include simplex if all pairs within distance ε
  • Čech complex — include simplex if balls have common intersection
  • VR is easier to compute — only needs pairwise distances
  • Filtration — nested sequence as ε increases from 0 to ∞
  • Birth time — smallest ε at which a simplex appears