Čech, Vietoris-Rips, Delaunay & Alpha Complexes | Applied Topology Tutorial

A simplex is a fundamental building block: 0-simplex is a point, 1-simplex is an edge, 2-simplex is a triangle, and so on. A simplicial complex is a collection of simplices closed under inclusion of faces - if a triangle exists, all its edges and vertices must exist. Faces are lower-dimensional simplices formed by omitting vertices; facets are maximal faces (highest-dimensional elements not faces of others). A pure complex has all facets of the same dimension. Not all complexes are manifolds: a discrete manifold requires purity, (d-1)-connectivity (any two d-simplices connected by (d-1)-simplices), and avoidance of pinches/folds. These conditions ensure the complex approximates a smooth manifold in the continuum limit. This foundational framework enables rigorous geometric analysis on discrete structures, bridging combinatorial topology with differential geometry.

An abstract simplicial complex is a non-empty collection of subsets of a finite vertex set V, satisfying two key properties: (1) every singleton subset containing a single vertex must be included, and (2) if a subset is in the complex, then all its non-empty subsets must also be included. Each subset is called a simplex, with its dimension defined as the cardinality minus one. The dimension of the entire complex is the maximum dimension of its simplices. A face is a subset of another simplex, and co-dimension measures the difference in dimensions. Examples include graphs (which are 1-dimensional simplicial complexes), solid k-simplices (containing all subsets of {0,1,...,k}), and hollow k-simplices (solid k+1-simplices minus the largest simplex).

An abstract simplicial complex is a mathematical structure consisting of a finite set of vertices V and a collection X of non-empty subsets of V called faces. The complex must satisfy two fundamental properties: (1) every singleton subset {v} for v in V must be in X, and (2) X must be closed under taking subsets—meaning if a face is in X, all its non-empty subsets must also be in X. Faces can be visualized geometrically: vertices as dots, edges as lines, triangles as lightly shaded triangles, and tetrahedrons as darkly shaded tetrahedrons. These visualization conventions help understand the hierarchical structure of the complex.

This section establishes the foundational concepts of simplicial complexes. A simplex is the convex hull of affinely independent vertices, with dimension equal to the number of vertices minus one. A geometric simplicial complex is a finite collection of simplices where any two intersect in a common face or are disjoint, and all faces of any simplex are included. An abstract simplicial complex is defined on a vertex set as a collection of subsets closed under taking subsets. The dimension of a face is its cardinality minus one. These definitions provide the combinatorial framework for studying geometric objects through their face structures.

Simplicial complexes provide the mathematical foundation for computational topology. An abstract simplicial complex is a collection of non-empty sets closed under taking subsets and containing all singleton vertex sets. Elements are called simplices: 0-simplices are points, 1-simplices are edges, 2-simplices are triangles, and higher-dimensional simplices represent cliques in graphs. This hierarchical structure enables decomposition into skeletons and facilitates computational implementation through matrix representations.

The Voronoi diagram is the dual graph of the Delaunay triangulation. Each vertex in the Voronoi diagram corresponds to a circumcenter of a Delaunay triangle, each region contains all points closest to a particular Delaunay vertex, and each edge represents the perpendicular bisector between two points. The Voronoi diagram can be used for nearest neighbor queries, where locating the query point within the Voronoi cell reveals the closest original point.

A Voronoi diagram partitions the plane into regions such that each region contains all points closer to its associated site (input point) than to any other site. Each Voronoi cell is convex and may be unbounded. The boundaries between cells occur where points are equidistant to two sites (forming edges) or three or more sites (forming vertices). The Delaunay triangulation connects neighboring sites whose Voronoi cells share an edge, forming a triangulation of the point set. These two structures are duals of each other: the adjacency relationships in one correspond to adjacency relationships in the other. Voronoi diagrams solve the nearest neighbor problem efficiently—once the diagram is built, determining the nearest site to any query point reduces to finding which Voronoi cell contains that point.

Voronoi diagrams partition a plane into proximity cells where each cell contains all points closer to its generator than any other, while Delaunay triangulation subdivides the convex hull of a point set into triangles with the property that no point lies inside the circumcircle of any triangle; these two structures are dual to each other, meaning they represent the same geometric information from complementary perspectives, and Delaunay triangulations can be efficiently constructed using an incremental algorithm that inserts points one by one and updates only the affected local triangles through edge flips to maintain the empty circumcircle property.

This section establishes the mathematical foundations of two fundamental computational geometry concepts. A Voronoi diagram partitions 2D space into polygons where each region contains all points closer to its associated seed point than any other. The Delaunay triangulation creates a mesh of triangles from seed points with the key property that no seed point lies inside the circumcircle of any triangle. These structures are duals of each other—the Voronoi vertices correspond to Delaunay circumcenters. The video demonstrates how to implement Delaunay triangulation using the d3-delaunay library in JavaScript, showing the conversion from p5.js vectors to the required array format and accessing triangle vertex indexes.

A Voronoi cell is unbounded if and only if its corresponding site lies on the boundary of the convex hull of the site set. Sites in the interior of the convex hull have bounded (convex polygon) cells. This relationship between the convex hull and Voronoi diagram structure is fundamental. The Delaunay triangulation and Voronoi diagram are dual structures: each Delaunay edge corresponds to a Voronoi edge, and each Delaunay triangle corresponds to a Voronoi vertex. The circumcenter of each Delaunay triangle is a Voronoi vertex, and the circumcircle contains exactly the triangle's vertices. This duality allows conversion between the two structures and enables transferring known results between them.

The n-th homology group Hₙ(X) = ker(∂ₙ)/im(∂ₙ₊₁) captures cycles (chains with no boundary) that aren't themselves boundaries. For finite simplicial complexes, chain groups are finitely generated abelian groups, decomposing as ℤ^r ⊕ torsion terms. The rank r is the n-th Betti number bₙ(X), representing the number of independent n-dimensional holes. The Poincaré polynomial P_X(t) = Σ bₙ(X)tⁿ encodes all Betti numbers, while the Euler characteristic χ(X) = P_X(-1) = Σ (-1)ⁿbₙ(X) provides a single numerical invariant. These tools compactly summarize topological structure.

Algebraic topology studies topological spaces by associating algebraic invariants to them, with homotopy groups and homology groups being fundamental tools; homotopy groups classify continuous maps between spaces up to deformation (homotopy), while homology groups capture n-dimensional 'holes' in spaces, and these invariants often form groups that provide powerful ways to distinguish and classify topological spaces.

Algebraic topology uses algebraic structures to study topological spaces, with homology being a fundamental concept that counts the number of holes in a space by examining collections of cells (zero-cells as points, one-cells as lines, two-cells as triangles) and their boundaries; specifically, an n-dimensional hole is defined as a collection of n-cells with boundary zero that is not the boundary of any (n+1)-cells, and homology groups capture these holes through the quotient of n-cycles by n-boundaries, with simplicial homology providing concrete computations while singular homology offers a more abstract, intrinsic formulation that proves equivalent to the cellular approach.

Betti numbers (β₀, β₁, β₂, ...) count holes of different dimensions: β₀ counts connected components, β₁ counts 1D cycles (loops), β₂ counts 2D enclosed volumes. A circle has β₀=1, β₁=1; a disk has β₀=1, β₁=0 (cycle shrinks); a sphere has β₀=1, β₁=0, β₂=1; a torus has β₀=1, β₁=2, β₂=1. Betti numbers are topological invariants, unchanged under continuous deformations. To formalize homology, simplices are oriented as ordered tuples with sign changes under permutation. An M-chain is a linear combination of oriented M-simplices. The boundary operator ∂ₘ maps M-chains to (M-1)-chains via alternating sums of faces. A fundamental property is ∂ₘ₊₁ ∘ ∂ₘ = 0 (boundary of a boundary is zero). An M-cycle has no boundary. The homology group Hₘ = Ker(∂ₘ) / Im(∂ₘ₊₁) captures non-trivial holes by quotienting out boundaries.

The n-th homology group Hₙ(X) = ker(∂ₙ)/im(∂ₙ₊₁) detects topological features. For S¹ triangulated with one 0-simplex and one 1-simplex, H₀(S¹) = Z (one connected component) and H₁(S¹) = Z (one hole). The Smith Normal Form is used to compute homology groups for more complex spaces like the Klein bottle. Homology groups provide algebraic invariants that distinguish topological spaces based on their shape and connectivity.