---
# System prepended metadata

title: 11. Some application of Homology group (2)

---

https://mds.marshall.edu/cgi/viewcontent.cgi?article=1674&context=etd
# The Jordan Curve Theorem
$\textbf{Theorem(Jordan Curve Theorem)}$ 
Let $h: S^1 \to S^2$ be an injective continuous map, so that $h(S^1)$ is a simple closed curve in $S^2$. Then $S^2 - h(S^1)$ consists of two connected components.

Homology and the Mayer–Vietoris sequence provide us with a completely rigorous proof. We will work with the sphere version, although the planar version is similar. (See Problem 6.) We break the circle $S^1$ up into two closed semicircles, which we call $C^+$ and $C^-$. Their intersection consists of two points. Let $A = S^2 - h(C^+)$ and $B = S^2 - h(C^-)$. Thus $A \cup B$ is a sphere with two points deleted. It is also easy to show that $A$ and $B$ are both homeomorphic to $\mathbb{R}^2$. The mystery is in $A \cap B$, which is $S^2 - h(S^1)$.

Our goal is to compute $H_0(A \cap B)$, because $H_0$ tells us the number of connected components. As we saw in the previous chapter, $H_0$ is always of the form $Z^r$ for some $r$, and in fact, $r$ is the number of connected components.

In order to compute $H_0(A \cap B)$, we throw $A$ and $B$ into the Mayer–Vietoris sequence and replace the terms we know. We already know the homology of $\mathbb{R}^2$ and of $S^1 \times \mathbb{R}$ (being homotopy equivalent to $S^1$), so we are only left with our mystery space. Starting with $H_2(A \cup B)$, the Mayer–Vietoris sequence becomes
\begin{equation}
0 \to H_1(A \cap B) \to 0 \to \mathbb{Z} \to H_0(A \cap B) \to \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \to 0 
\end{equation}Because $H_1(A \cap B)$ is surrounded by zeros, it is zero, although this is not of major concern to us. We now compute $H_0(A \cap B)$. We use a similar trick to the one we used when showing that the alternating sum of the Betti numbers is the Euler characteristic: ==in an exact sequence bounded by zeros, the alternating sum of the ranks is $0$.== We know all the ranks in the exact subsequence
\begin{equation}
0 \to \mathbb{Z} \to H_0(A \cap B) \to \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \to 0 
\end{equation}so we can compute the rank of $H_0(A \cap B)$, which is $2$. Since $H_0$ is of the form $Z^r$, we must have $r = 2$. Thus $A \cap B$ consists of two connected components, and we’re done.

# The Hurewicz Map
$\textbf{Definition}$ 
Let $G$ be a group. Its commutator subgroup is the subgroup $[G, G]$ generated by all elements of the form $[g, h] = ghg^{-1}h^{-1}$.

$\textbf{Proposition}$ 
The commutator subgroup $[G, G]$ is a normal subgroup of $G$.

$\textbf{Proof}$ 
A typical element of $[G, G]$ has the form
\begin{equation} 
a = [g_1, h_1][g_2, h_2]\dots[g_k, h_k]. 
\end{equation}Let $g \in G$ be any element. Then
\begin{equation}
gag^{-1} = [gg_1g^{-1}, gh_1g^{-1}]\dots[gg_kg^{-1}, gh_kg^{-1}], 
\end{equation}which is an element of $[G, G]$.

$\textbf{Definition}$ 
The $\textit{abelianization}$ of a group $G$ is the quotient group $G^{\text{ab}} = G/[G, G]$.

For any group $G$, $G^{\text{ab}}$ is an abelian group. In fact, it is the largest abelian group that is a quotient of $G$. If we have a presentation for $G$, with some generators and relations, then we obtain the abelianization by adding the extra relations that force any pair of generators to commute, and no others.

$\textbf{Example}$ 
Let $G = \langle a_1, \ldots, a_n \mid \rangle$ be a free group on $n$ generators. Then its abelianization is
\begin{equation}
G^{\text{ab}} = \langle a_1, \ldots, a_n \mid a_ia_j = a_ja_i \rangle \cong \mathbb{Z}^n.
\end{equation}
is the free $abelian$ group on n generators.

We can now state Hurewicz’s Theorem in the case of $\pi_1$ and $H_1$. (Hurewicz more generally gives a relation between $\pi_n$ and $H_n$ in the case that $\pi_0, \pi_1, \ldots, \pi_{n-1}$ are all trivial.)

$\textbf{Theorem(Hurewicz)}$ 
If $X$ is path-connected and $x \in X$ is a basepoint, then
\begin{equation}
H_1(X) \cong \pi_1(X, x)^{ab}.
\end{equation}

We will not give a complete proof of Hurewicz’s Theorem, but we can at least give an outline of how the argument might go. Suppose we have any loop $\gamma$ in $X$ based at $x$. Then we can break up $\gamma$ into a bunch of 1-simplices whose sum is a 1-cycle in $X$. (This is more subtle than it may appear, because $\gamma$ does not necessarily live in the 1-simplices of $X$. So, we may have to subdivide it first and perhaps homotope it slightly.) One can then check that two homotopic loops give rise to two 1-chains that only differ by a boundary, namely the boundary of the region between the two loops. See Figure 14.1 for a picture. As a result, we obtain a map, called the Hurewicz map, from $\pi_1(X, x)$ to $H_1(X)$. In fact, the Hurewicz map is a homomorphism.
![image](https://hackmd.io/_uploads/H1coSk5BT.png)

Next, we must check that the Hurewicz map is surjective, and that its kernel is $[\pi_1(X, x), \pi_1(X, x)]$, the commutator subgroup of the fundamental group. This is believable: If we have a cycle in $X$, we can break it down as a bunch of loops, then we can add tails to each one of the loops so that they become based at $x$, as shown in Figure 14.2. Once we check the details, this shows that the Hurewicz map is surjective. The trickiest part is showing that the kernel is the commutator subgroup. Since $H_1(X)$ is abelian, we know that the kernel of the Hurewicz map is at least as large as the commutator subgroup. But one must show that it is no larger. And that is the part that we will skip.

![image](https://hackmd.io/_uploads/SykbI1qSa.png)

# Delaunay and Regular Triangulation
$\textbf{Definition}$
Given a point cloud, $K_0$ (vertices), of a simplicial complex $K$ of dimension $n$, the Delaunay Triangulation is the unique simplicial complex of $K$ such that for any $n$-simplex $\delta \in K$, the circumsphere of $\delta$ contains no points of $K_0$ other than those that make up the vertices of $\delta$. This is called the Delaunay Property.

![image](https://hackmd.io/_uploads/ryvQBLuST.png)

$\textbf{Definition}$ 
Given an $n$-simplex with $n+1$ balls $B_i$ at its vertices, the orthosphere is the unique sphere $U$ such that $U$ is tangent to all $B_i$. (See image below.) The center of this sphere is called the orthocenter, and likewise, the radius of this sphere is called the orthoradius.

![image](https://hackmd.io/_uploads/B1wIS8dHT.png)

$\textbf{Definition}$ 
Given $K_0$, a vertex set in $\mathbb{R}^n$, and a set of weights associated with each $\delta \in K_0$, the Regular Triangulation is the unique simplicial complex such that for any $n$-simplex $\delta \in K$, the orthosphere of $\delta$ contains no points of $K_0$ other than those that make up the vertices of $\delta$.


The algorithm for Delaunay Triangulation of a point cloud in $\mathbb{R}^3$ is designed to handle vertices in higher dimensions as well. The idea behind the incremental algorithm to compute the Delaunay Triangulations of a vertex set is to begin with a Delaunay Triangulation (a single tetrahedron), add vertices one at a time, and add/remove higher-dimensional simplices as needed to maintain the Delaunay Property. The only data structures we will need to maintain for this algorithm are a list of vertices, a list of tetrahedra, and a buffer. We must also be able to store the center and radius of the circumsphere of each tetrahedron.

We begin by creating the single tetrahedron mentioned above. To keep the algorithm as simple as possible, we will create a bounding tetrahedron by choosing its 4 vertices such that the tetrahedron contains the point cloud. In $\mathbb{R}^3$, this is obtained by bounding the vertices in a cube (using the maximum coordinate value), circumscribing the cube by a sphere, and circumscribing the sphere by a tetrahedron. We will call the vertices of this tetrahedron $v_1, v_2, v_3,$ and $v_4$. This can also be generalized to higher dimensions. We will refer to the lists of vertices ($K_0$) and tetrahedra as $V$ and $T$ respectively, and we will call the buffer for storing faces $B$. We must have a function $\text{IsInTetCircum(point, tetrahedron)}$ to determine if a point is contained in the circumsphere of the tetrahedra. We will use the notation $\text{Buffer += x}$ for adding an element to the buffer and $\text{Buffer -= x}$ for removing an element from the buffer.

$\textbf{Algorithm}$ 
Let $B$ be a bounding tetrahedron

![image](https://hackmd.io/_uploads/H1UqdLuST.png)

This algorithm begins with the bounding tetrahedron. Next, the algorithm finds all tetrahedra whose circumsphere contains the point added, $p_i$. It then stores the faces of these tetrahedra in $B$ and deletes the tetrahedra from $T$. Next, it deletes any faces from $B$ that are not unique. Then, a new tetrahedra is added to $T$ from each face in $B$ to $p_i$. $B$ is now emptied, and we add the next point. This continues until all points in $V$ have been added. In the final step, the algorithm removes the bounding tetrahedron from $T$, and it removes the associated vertices from $V$. We are left with the Delaunay Triangulation of the point cloud $V = K_0$.

$\textbf{Remark}$ 
Edelsbrunner describes a similar algorithm for computing a Delaunay Triangulation. What he does differently is, rather than finding all tetrahedra whose circumsphere contains a newly added point, he finds the one tetrahedron that contains the point. Then, he finds a neighboring tetrahedron whose circumsphere contains the point and performs a series of topological flips to change the local tetrahedra. This is far more difficult to implement but provides the same results.

This algorithm can be generalized to produce a Regular Triangulation simply by
replacing the circumsphere of each tetrahedron with the orthosphere.

# Betti Numbers
$\textbf{Definition}$ 
A filtration $F$ is an ordering of simplices in a simplicial complex.

This filtration may be random or determined by the needs of a specific application. The filtered complex will be the only input for our algorithm to compute Betti Numbers. Our growing complex will be created by adding the simplices in the order determined by the filtration.

This algorithm will calculate the Betti numbers for a simplicial complex of dimension 3, therefore, we will call each simplex either a vertex, edge, triangle, or tetrahedron.We begin by running through all simplices of a filtration $F$, marking all $k$-simplices that form a $k$-cycle. We will need data structures to maintain a list of simplices of each type. We must also be able to store values (true/false) to mark each simplex as completing a cycle or not. Furthermore, we will need to store a component number for each vertex and triangle.

$\textbf{Marking vertices:}$ 
All vertices are initially 0-cycles and therefore will be marked.

$\textbf{Marking edges:}$
To mark edges, we must begin with the set of all vertices. Initially, each vertex is a component. For each edge, as it appears in the filtration, consider the two vertices forming the edge.
- If the component numbers of the vertices are different (say, $a$ and $b$), we must change all of the component numbers in the vertex list that are equal to $b$ to $a$. Since the component numbers are different, we know that the vertices were from different components, and by adding the edge, we joined them, thereby removing a 0-cycle. This edge will not be marked.
- Otherwise, if the component numbers of the two vertices are the same, then by adding the edge, we have created a new 1-cycle. Therefore, we will mark this edge.

$\textbf{Marking triangles}$
Deciding whether to mark triangles is a bit more difficult. We will use a dual graph, defined as follows. We will consider the tetrahedra as nodes and each triangle as an edge between the nodes if the triangle is a face of both tetrahedra represented by the nodes. We will be working backward through the filtration, removing simplices, considering only triangles. We will begin with a unique component number assigned to each tetrahedron. As we add each triangle, consider the two tetrahedra that it connects.
- If the component numbers of the nodes are different (assume we have component values $a$ and $b$), you must change all of the component numbers in the node list that are equal to $b$ to $a$. Since the component numbers are different, we know that this triangle splits two tetrahedra. Therefore, it creates a 2-cycle, and we will mark it.
- Otherwise, if the component numbers are the same, then by adding the triangle, we have filled a 1-cycle. Therefore, we will not mark this triangle.

$\textbf{Marking tetrahedra:}$
No tetrahedra will be marked except for the last tetrahedron to complete a triangulation. This is because this is the only tetrahedron that completes a 3-cycle.

$\textbf{Betti Algorithm:}$

$\textbf{Algorithm}$
Let $S$ be a filtered complex with $n$ simplices.
![image](https://hackmd.io/_uploads/S1c5zwdSa.png)

# Alpha Shapes
We begin with the set points in $\mathbb{R}^n$. We can enlarge all points (turn points into balls) by a value called $\alpha$ to form balls centered at the point with radius $\alpha$. As we increase $\alpha$, and hence the balls, we are in essence building a simplicial complex as before. Another way of describing this is that as $\alpha$ grows, the level of detail in the complex goes from fine to coarse. In the case of weighted points, we start with the balls with radius equal to the square weight, and add $\alpha$ to that radius.

We build the complex as follows. As $\alpha$ grows, when two balls become tangent, we add an edge between them to the complex. A triangle is added when the $\alpha$-balls located at its vertices cover the triangle. Likewise, a tetrahedron is formed when the $\alpha$-balls located at its vertices cover the tetrahedron. The value of $\alpha$ at which we add each simplex is called the birth of the simplex. After we determine the birth of each simplex, we create a filtration by ordering the simplices in the complex by birth. In the case of a tie, the lower-dimensional simplex is placed first. This process yields a family of Alpha Shapes, defined as follows.

$\textbf{Definition}$ 
An Alpha Shape is a simplicial complex obtained by taking a vertex set and a particular value of $\alpha$ and calculating the edges, triangles, and tetrahedra from the $\alpha$-balls as described above.

$\textbf{Definition}$ 
An Alpha Complex is the filtration of all Alpha Shapes for all values of $\alpha$ with $-\infty < \alpha < \infty$.

An Alpha Complex is a filtration. In the alpha shape, for sufficiently small $\alpha$, you get only the point set. For sufficiently large $\alpha$, you get the ==convex hull of the point cloud==. As $\alpha$ increases, the complex grows. If we use the incremental algorithm for calculating Betti numbers on this filtration, we get the Betti numbers at each stage in the building process. This can be far more valuable than simply knowing the Betti number for the Delaunay Triangulation. There may be tunnels or voids that are 'almost' closed (for example, a "C" shape or a pocket) that would have been missed by the Betti numbers of the complex but can be seen by looking at the Betti numbers of the Alpha Shapes. We can also get an idea of the size of the hole by varying $\alpha$.

In applications, Homology groups have several limitations. The Betti numbers for a complex may be very large due to small cycles originating from errors in measurement or minor structures in the complex, which may limit the usefulness of Homology groups. Furthermore, shapes such as the letter "C" may be nearly a cycle, but not quite. In applications, we may want to capture these structures as well. To remove noise and to enable us to describe a larger class of shapes, we will develop "persistent homology".

In the last section, we developed the idea of a filtration. In the case of a filtration arising from Alpha Shapes, we can think of the filtration as the life-span of a growing complex. In this growing complex, cycles are continuously forming and collapsing. We can learn a great deal from looking at the amount of time it takes for the cycle to collapse after it is created. This leads us to the following definition.

$\textbf{Definition}$ 
Persistence is a measure of the importance of an $n$-cycle, defined to be the difference between the $\alpha$ for which the cycle is created, to the $\alpha$ it is filled by adding an $(n+1)$-simplex.

$\textbf{The Algrithmn}$
Edelsbrunner describes the following algorithm for computing the persistence of Betti Numbers of a simplicial complex (14). As in the Algorithm for the calculation of Betti Numbers, we will need to mark each simplex in the filtration as either completing a cycle or not, called a "positive cycle" or a "negative cycle". We use this terminology because in our filtration, the addition of each cycle either creates or destroys a cycle. We would like to build a list of cycles, while maintaining the $\alpha$ of death and $\alpha$ of birth of them. We will run through the filtration, and each time we add a negative simplex, we will note the $\alpha$ and run a subalgorithm to determine the $\alpha$ of birth of the cycle destroyed by this simplex. We will end up with a list of times of birth and death from which we can determine the persistence of each cycle, and the persistent homology groups of the complex.



