Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Alpha Complexes and Delaunay Triangulations

3 minute read

Published:

TL;DR: The alpha complex at scale α is the restriction of the Delaunay triangulation to simplices whose circumradius is at most α. As α grows from 0 to ∞, we get the alpha filtration. By the nerve theorem, its persistent homology equals that of the union of balls — but with far fewer simplices, making it the preferred method for low-dimensional data.

Voronoi Diagrams and Delaunay Triangulations

For a finite point cloud \(P \subset \mathbb{R}^d\), the Voronoi cell of point \(p \in P\) is the region closer to \(p\) than to any other point:

\[V(p) = \{x \in \mathbb{R}^d : \|x - p\| \leq \|x - q\| \text{ for all } q \in P\}\]

The Voronoi diagram partitions \(\mathbb{R}^d\) into Voronoi cells. Its dual is the Delaunay triangulation \(\mathrm{Del}(P)\): connect points \(p, q \in P\) iff their Voronoi cells share a face. The Delaunay triangulation is the unique triangulation that maximises the minimum angle among all triangulations (in 2D).

The Alpha Complex

The alpha complex \(\mathrm{Alpha}(P, \alpha)\) is the sub-complex of the Delaunay triangulation consisting of simplices whose circumscribed ball has radius at most \(\alpha\):

$$\mathrm{Alpha}(P, \alpha) = \{\sigma \in \mathrm{Del}(P) : r(\sigma) \leq \alpha\}$$

where \(r(\sigma)\) is the radius of the smallest enclosing ball of \(\sigma\) whose centre lies in the intersection of Voronoi cells of \(\sigma\)’s vertices (the “Delaunay ball”).

As \(\alpha\) increases from 0 to ∞, simplices enter one by one, giving the alpha filtration \(\mathrm{Alpha}(P, 0) \subseteq \mathrm{Alpha}(P, \alpha_1) \subseteq \cdots \subseteq \mathrm{Del}(P)\).

Why Alpha Complexes Are Preferred

Size advantage: The Delaunay triangulation in \(\mathbb{R}^d\) has \(O(n^{\lceil d/2 \rceil})\) simplices. For \(d = 2\), this is \(O(n)\); for \(d = 3\), \(O(n^2)\). The Vietoris-Rips complex at the same scale has \(O(n^k)\) simplices for all \(k \leq d\), which is much larger.

Homotopy equivalence: By the nerve theorem, \(\mathrm{Alpha}(P, \alpha)\) is homotopy equivalent to \(\bigcup_{p \in P} B(p, \alpha) \cap V(p)\), which is itself homotopy equivalent to \(\bigcup_{p \in P} B(p, \alpha)\) (the union of balls). Therefore, the persistent homology of the alpha filtration equals the persistent homology of the union-of-balls filtration — the topologically correct answer.

Key Insight: The Vietoris-Rips complex is an approximation to the Čech complex (which equals the union-of-balls by the nerve theorem). The alpha complex IS the Čech complex restricted to the Delaunay triangulation — it computes the exact same persistent homology but with far fewer simplices. For data in ℝ² or ℝ³, always prefer alpha over Vietoris-Rips.

Weighted Alpha Complexes

The weighted alpha complex extends this to points with weights (e.g., atomic radii in molecular data). The distance from point \(x\) to a weighted point \((p, w_p)\) becomes the power distance:

\[\pi(x, p) = \|x - p\|^2 - w_p\]

Weighted alpha complexes produce the power diagram (weighted Voronoi) and its dual (regular triangulation). Used in GUDHI for molecular topology.

References

  • H. Edelsbrunner, D. Kirkpatrick, R. Seidel, “On the Shape of a Set of Points in the Plane,” IEEE Trans. Inform. Theory, 1983.
  • H. Edelsbrunner & J. Harer, Computational Topology, Chapter III.
  • GUDHI library: gudhi.inria.fr

You May Also Enjoy

GAPE: Remember to Forget — Gated Adaptive Positional Encoding

4 minute read

Published:

GAPE is a drop-in RoPE augmentation that adds content-aware attention logit biases: a query-gate suppresses irrelevant distant context while a key-gate preserves salient distant tokens. Provably sharper attention and improved long-context robustness — no architecture changes needed.

PolyNSD: Polynomial Neural Sheaf Diffusion

4 minute read

Published:

PolyNSD replaces the NSD propagation operator with a degree-K Chebyshev polynomial in the normalised sheaf Laplacian, achieving SOTA on homo- and heterophilic benchmarks with only diagonal restriction maps and dramatically lower memory usage.

TDA in Materials Science: Topology of Structure and Phase

3 minute read

Published:

Persistent homology characterises the multi-scale structure of materials — from pore geometry in catalysts to glass transition in amorphous materials. H₀ captures connectivity, H₁ captures channels and rings, H₂ captures enclosed voids. These topological descriptors predict mechanical properties, adsorption capacity, and phase transitions more accurately than geometric averages.

TDA in Drug Discovery: Molecular Topology

3 minute read

Published:

Persistent homology provides multi-scale topological fingerprints of molecular structures — capturing rings, cavities, and protein pockets that traditional cheminformatics descriptors miss. Applications include binding site detection, ADMET property prediction, and protein-ligand interaction modelling.