An important feature of a galaxy is its topology. Does the galaxy distribution consist of isolated high-density clumps (meatball topology), does it have isolated voids surrounded by walls (bubble topology), or does it resemble a sponge, with interlocked high- and low-density regions?
The standard first step is to turn galaxies, which are represented by finite set of points, into smooth surfaces in 3-space. To do so choose a weighting function (a Gaussian) convolving with each point. This induces a continuous density function throughout the sky. Isodensity contours form the surfaces whose topology we wish to compute. The Gauss-Bonnet formula allows us to express the genus of the surface in terms of the integral of the Gaussian curvature. The integral is computed by sampling the surface by a fine enough grid. These techniques work fairly well and have been used to determine the topology of many galaxies from satellite observations [106].
Alternatively, the points can be connected to form a simplicial complex. Instead of a weighting function we choose a spherical ball around each point and consider the boundary of the union of balls. To compute the components of this surface and the genus of each component, we convert the union of balls into a complex as follows. First, clip the balls to within their Voronoi cells. The resulting cells overlap along their boundaries. The alpha complex represents pairwise, triplewise, and quadruplewise overlap by edges, triangles, and tetrahedra. The complex is homotopy equivalent to the union of balls [46], and there is a fast linear space algorithm that computes the three betti numbers. The number of surfaces, their genuses, and how they are nested is readily derived from this information.
If other parameters are taken into account, the dimension of the ambient space shoots up and to reveal the full topology is more difficult. Of all the topological invariants, the homology groups are the most popular, mostly because of their computational tractability. The homology groups describe the cycle structure of a topological space. It would be extremely useful to be able to compute homology groups efficiently for low-dimensional geometric complexes. Outside astrophysics, there are many important applications in pattern recognition and classification in biology and chemistry as well as in robotics and scene analysis. Comparing homologies is a good (if not foolproof) test to rule out topological equivalence: two spaces with different homologies cannot be homeomorphic; of course, the converse is not true.
There are also applications to the classification of time series
and the analysis of dynamical systems.
Spectral analysis has long been the standard tool for classifying
time series.
In the absence of sharp harmonics, the signal is dismissed as noise.
This might be a mistake.
Analysis for nonlinear dynamics can be done by computing topological
invariants of the attractor set for the system being measured.
To do so one can map the time series into
(
) by scanning a ``comb'' of length
across the
series and thinking of each
-tuple of entries at the teeth
as a point in
.
By grouping all
-tuples of points at a distance
less than
from one another, one can define
-simplices.
Finally, by introducing the obvious boundary operators, this
yields a complex whose (Cech) homology is called
the
-homology of the set.
Because Cech homology commutes with inverse limits, this is
an appropriate method for computing the homology of the attractor.
Moreover the use of
-homology (where simplices are
defined only in terms of pairwise distances) should
have computational advantages.
This is similar to the idea of alpha complex alluded to in
the earlier paragraph.
Computing homology groups, or their ranks referred to as betti
numbers, can be done by algebraic methods, but it is often inefficient.
Exploiting the specific geometry of the manifolds can lead to
much faster algorithms.
There is a compelling analogy with graph algorithms.
Many problems on graphs can be phrased algebraically
and solved by inverting linear systems.
That is not the way it is done, however.
Graph algorithms seek to exploit the inner combinatorial
structure of graphs to avoid generic algebraic treatments.
Similarly, computational geometry can be used to
bypass linear algebra in the computation of homologies.
An example is the algorithm for simplicial complexes embedded
in described in [42].
In particular, the use of Mayer-Vietoris sequences should be
useful in designing efficient divide-and-conquer schemes for
computing the homology of higher-dimensional complexes
by computational geometric means.