# An Efficient Data Retrieval Parallel Reeb Graph Algorithm
## 2 Morse Theory and Reeb Graphs
### Morse Theory  
Morse Theory is a tool from differential topology that is concerned with the relations between the geometric and topological aspects of manifolds and the real-valued functions that are defined on them. One of the primary interests in this theory is the relationship between the topology of a smooth manifold \(M\) and the critical points of a real-valued smooth function \(f\) defined on \(M\). Intuitively, Morse theory studies the topological changes of the level sets of a real-valued smooth function as the height of \(f\) varies. [PERSON] [68] first introduced Morse theory for infinite dimensional spaces. A comprehensive introduction to Morse theory on finite-dimensional manifolds is given in [69]. Additionally, see [66; 67]. Morse theory has been proven to be a very useful tool in computer graphics and geometric data processing and understanding. The theory was extended to triangulated 2-manifolds by [70]. Recently, [PERSON] theory has found applications in global surface parameterization [71], finding a fundamental domain of a surface [72], surface quadrangulation [73], topological matching [27], implicit surfaces [74], surface segmentation [75], spline construction [76], and many other applications. Let \(M\) be a compact and smooth \(n\)-manifold and let \(I=[a,b]\subseteq\mathbb{R}\), where \(a<b\), be a closed interval. Let \(f:M\longrightarrow I\) be a smooth function that is defined on \(M\). A point \(x\in M\) is called a critical point of \(f\) if the differential \(df_{x}\) is zero. A value \(c\) in \(\mathbb{R}\) is called a critical value of \(f\) if \(f^{-1}(c)\) contains a critical point of \(f\). A point in \(M\) is called a regular point if it is not a critical point. Similarly, if a value \(c\in\mathbb{R}\) is not a critical value, then we call it a regular value. The inverse function theorem implies that for every regular value \(c\) in \(I\), the level set \(f^{-1}(c)\) is a disjoint union of \(n-1\) manifolds. In particular, when \(n=2\), then \(f^{-1}(c)\) is a disjoint union of simple closed curves. A critical point is called non-degenerate if the matrix of the second partial derivatives of \(f\), called the Hessian matrix, is non-singular. A differentiable function \(f:M\longrightarrow I\) is called Morse if all of its critical points are non-degenerate, and all critical values are distinct. If the manifold \(M\) has a boundary, i.e., \(\partial M\
eq\emptyset\), then we will also require two other conditions: (1) \(f^{-1}(\partial I)=\partial M\) and (2) there are no critical points on \(\partial M\). In other words, the boundary points in the interval \(I\), the values in \(\partial I\), are regular values for the function \(f\). The index of a critical point \(x\) of \(f\), as denoted by \(index_{f}(x)\), is defined to be the number of negative eigenvalues of its Hessian matrix. For instance, the Hessian of a scalar function on a smooth surface is a \(2\times 2\) symmetric matrix. Hence, the index of \(f\) on a critical point takes the values \(0\), \(1\), or \(2\)In this case, an index \(0\), \(1\), or \(2\) of a critical point of a function \(f\) is nothing more than a local minimum, a saddle, or a local maximum for \(f\), respectively. If \(f\) is a Morse function on a surface, then, up to a change of coordinates, the surface around a critical point \(f\) has one of the simple forms as appear in Figure 1. More formally, we have the following important Lemma:  
**Lemma 1**. : _(Morse Lemma) Let \(M\) be a smooth surface, \(f:M\longrightarrow\mathbb{R}\) be a smooth function, and \(p\) be a non-degenerate critical point of \(f\). We can choose a chart \((\phi,U)\) around \(p\), such that \(f\circ\phi^{-1}\) takes exactly one of the following three forms:_  
1. _Local minimum--_\(f\circ\phi^{-1}(X,Y)=X^{2}+Y^{2}+c\)__
2. _Saddle--_\(f\circ\phi^{-1}(X,Y)=X^{2}-Y^{2}+c\)__
3. _Local maximum--_\(f\circ\phi^{-1}(X,Y)=-X^{2}-Y^{2}+c\)__  
An analogous lemma holds for Morse functions on higher dimensional smooth manifolds. See [66] for more details.