Topology of random geometric complexes: a survey <s> Homology and Betti Numbers <s> A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, " \alpha -shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimal O(n \log n) algorithm that constructs \alpha -shapes is developed. <s> BIB001 </s> Topology of random geometric complexes: a survey <s> Homology and Betti Numbers <s> The Betti numbers are fundamental topological quantities that describe the k-dimensional connectivity of an object: B_0 is the number of connected components and B_k effectively counts the number of k-dimensional holes. Although they are appealing natural descriptors of shape, the higher-order Betti numbers are more difficult to compute than other measures and so have not previously been studied per se in the context of stochastic geometry or statistical physics. ::: As a mathematically tractable model, we consider the expected Betti numbers per unit volume of Poisson-centred spheres with radius alpha. We present results from simulations and derive analytic expressions for the low intensity, small radius limits of Betti numbers in one, two, and three dimensions. The algorithms and analysis depend on alpha-shapes, a construction from computational geometry that deserves to be more widely known in the physics community. <s> BIB002 </s> Topology of random geometric complexes: a survey <s> Homology and Betti Numbers <s> We study the expected topological properties of Cech and Vietoris–Rips complexes built on random points in ℝd . We find higher-dimensional analogues of known results for connectivity and component counts for random geometric graphs. However, higher homology H k is not monotone when k>0. ::: ::: In particular, for every k>0, we exhibit two thresholds, one where homology passes from vanishing to nonvanishing, and another where it passes back to vanishing. We give asymptotic formulas for the expectation of the Betti numbers in the sparser regimes, and bounds in the denser regimes. <s> BIB003 </s> Topology of random geometric complexes: a survey <s> Homology and Betti Numbers <s> There have been several recent articles studying homology of various types of random simplicial complexes. Several theorems have concerned thresholds for vanishing of homology, and in some cases expectations of the Betti numbers. However little seems known so far about limiting distributions of random Betti numbers. ::: In this article we establish Poisson and normal approximation theorems for Betti numbers of different kinds of random simplicial complex: Erd\H{o}s-R\'enyi random clique complexes, random Vietoris-Rips complexes, and random \v{C}ech complexes. These results may be of practical interest in topological data analysis. <s> BIB004 </s> Topology of random geometric complexes: a survey <s> Homology and Betti Numbers <s> Cech and Vietoris-Rips complexes. In particular, we obtain results about homology, as measured via the growth of Betti numbers, when the vertices are the points of a general stationary point process. This significantly extends earlier results in which the points were either iid observations or the points of a Poisson process. In dealing with general point processes, in which the points exhibit dependence such as attraction, or repulsion, we find phenomena quantitatively different from those observed in the iid and Poisson cases. From the point of view of topological data analysis, our results seriously impact on considerations of model (non) robustness for statistical inference. <s> BIB005 </s> Topology of random geometric complexes: a survey <s> Homology and Betti Numbers <s> We consider the topology of simplicial complexes with vertices the points of a random point process and faces determined by distance relationships between the vertices. In particular, we study the Betti numbers of these complexes as the number of vertices becomes large, obtaining limit theorems for means, strong laws, concentration inequalities and central limit theorems. As opposed to most prior papers treating random complexes, the limit with which we work is in the so-called ‘thermodynamic’ regime (which includes the percolation threshold) in which the complexes become very large and complicated, with complex homology characterised by diverging Betti numbers. The proofs combine probabilistic arguments from the theory of stabilizing functionals of point processes and topological arguments exploiting the properties of Mayer–Vietoris exact sequences. The Mayer–Vietoris arguments are crucial, since homology in general, and Betti numbers in particular, are global rather than local phenomena, and most standard probabilistic arguments are based on the additivity of functionals arising as a consequence of locality. <s> BIB006
Recall that the i-th Betti number β i is the dimension of i-th homology, i.e. As mentioned in the introduction, the homology groups H i (i ≥ 1) basically describe cycles (or holes) of different dimensions, and thus the Betti numbers represent the number of cycles. Betti numbers of random geometric complexes were first studied by Robins in BIB002 . Robins studies "alpha shapes" on random point sets BIB001 , which are topologically equivalent toČech complexes but more convenient from the point of view of computation. The underlying distributions are uniform on a d-dimensional cube, but to avoid boundary effects periodic boundary conditions are imposed. Robins computes the expected Betti numbers over a large number of experiments. Furthermore, she explains the shapes of these curves in the "small radius-low intensity" regime, writing formulas in the d = 2 and d = 3 cases. The study of the limiting Betti numbers was revisited and significantly extended later in a series of papers by various authors BIB003 BIB004   BIB006 BIB005 . In contrast to connectivity which corresponds to reduced zeroth homologyH 0 , the higher homology of random geometric complexes H i (C(n, r)), i ≥ 1 is not monotone with respect to r. Each homology group passes through two main phase transitions, one where it appears and one where it disappears. For the randomČech complex, the phase transition where H i appears occurs ). This radius is within the subcritical regime (nr d → 0). In this regime the complex is sparse and highly disconnected which allows very precise Betti number computations -in particular we will see The phase transition where the i-th homology vanishes depends on the underlying probability distribution, but if f has a compact support then we will see that it occurs at r = Θ((log n/n) 1/d ) (or nr d = Θ(log n)), which is within the supercritical regime. This radius is similar to the connectivity threshold we saw in Section 3.3, though the constants are different. While not entirely revealed, the exact vanishing radius for the different homology groups H i depends on i, although the differences will show up as a second order term. We will discuss this briefly in Section 6. In the critical regime the analysis of the Betti numbers β i (n, r), i ≥ 1, is significantly more complicated than the analysis of β 0 (n, r). In this case we will see that β i (n, r) = Θ(n), however the limiting constants are unknown to date. We now overview the topology of random geometric complexes for each of the regimes. 4.1. The subcritical regime. The work in BIB003 BIB004 provides a detailed study for the Betti numbers in the subcritical regime. Since a random geometric complex in this regime is so sparse, the vast majority of i-cycles are generated by "small" sphere-like shapes, with the minimum number of vertices possible. For theČech complex, the minimum number of vertices to form an i-cycle is i+2 (for example, to create a 1-cycle, or a loop, we need at least 3 vertices). These sphere-like formations are local features, so by the rule of thumb above, we might expect a theorem that holds across a wide class of measures. A key ingredient in the results is the following indicator function testing whether a minimal set forms an i-cycle or not. The following theorem provides the limit for the expected Betti numbers. as n → ∞, where Note that within the subcritical regime the limit of the last term can be either zero, a finite number, or infinity (for different choices of r). Combining with the second moment method, this is the threshold radius for the phase transition where homology first appears. (1) If then a.a.s. H i (C(n, r)) = 0, and (2) if Thus, the threshold where the i-th homology first appears is nr The parallel result for Vietoris-Rips complexes is also given in BIB003 .  as n → ∞, where C i is defined in Theorem 4.1. When r is above the threshold, the number of cycles goes to infinity, and with the proper normalization it obeys a central limit theorem. Let N (0, 1) denote a normal distribution with mean 0 and variance 1.  as n → ∞. Again, because we are in the subcritical regime, these results hold for a wide variety of measures-whenever the underlying probability measure has a measurable density function which is bounded above. They hold even without compact support, for example for a multivariate normal distribution. In In the critical regime a giant connected component emerges -see the discussion in Section 3.2 on percolation theory -and this significantly complicates the analysis. To date, there has been some partial progress in studying these cases. For example, we have the following result for expectation.  A parallel theorem in BIB003 gives the same result for the Vietoris-Rips complex, but in this case one does not require the assumption that i ≤ d − 1; in the critical regime, β i is growing linearly for every i ≥ 0. The last theorem provides us with the expected order of magnitude of the Betti numbers, but the actual constants have not yet been discovered. Nevertheless, recent work by Yogeshwaran et al. BIB006 gives laws of large numbers and central limit theorems for Betti numbers of randomČech complexes in the thermodynamic limit. We state here a few of these results relevant for theČech complex C(n, r). The following law of large numbers, is Theorem 4.6 in BIB006 . Theorem 4.7 (Yogeshwaran et al., BIB006 ). If nr d → λ ∈ (0, ∞), then for each The version of the central limit theorem proved in BIB006 is for an underlying uniform distribution, and for simplicity assumes that it is supported on the unit cube in R d . In this case, they define I d (P) as an interval in R whose endpoints are related to different modes of percolation, and then prove the following.