Topological Data Analysis - Combinatorial Representations

Combinatorial Representations

1. Cech Complex. The Cech complex is the nerve of the cover of balls of radius around each point in a set. Since balls are convex and convex sets are contractible, its nerve captures the topology of the cover. The Cech Complex is not computed in practice due to its computational complexity. The uniform ball radii imply an assumption of uniform sampling on the input, which is not valid in a real world dataset. Non-uniform radii methods can also be used, such as in the case of the Alpha Simplex.
2. Alpha Complex. The Voronoi diagram is the set of all Voronoi regions for the points in . This diagram is considered a closed cover for . The Delaunay complex is the nerve of the Vornoi diagram. The Voronoi cover and its nerve are fundamental geometric objects and have been extensively studied within computational geometry. Alpha complexes are constructed by first building the Delaunay complex. For each simplex of the Delaunay complex, we compute the minimum scale at which each simplex enters the alpha complex. Then the simplices are sorted by their minimum scale to get a partial order of simplices. The alpha complex is not formed with any scale using this ordering. Efficient algorithms and software exist for computing Delaunay complexes, and in turn, alpha complexes in 2 and 3 dimensions. However, the construction of the Delaunay complex is difficult in higher dimensions.
3. Vietoris-Rips complex