# An Efficient Data Retrieval Parallel Reeb Graph Algorithm
## 5 Parallelization of the Algorithm
### The Partition Stage  
In this first stage of the parallel algorithm, we sort the vertices of the manifold with respect to the function \(f\). This step can be done efficiently in parallel [77; 78]. The critical sets for saddle points are then determined by assigning a thread to each saddle point. This computation is only necessary to determine the number of ascending paths that we need to initiate from that saddle point. Next, we partition the manifold \(M\) to submanifolds along with certain regular values of the scalar function \(f\). More precisely, the partition stage is given, as follows:  
1. Compute the critical points of \(f\) by assigning a thread to each vertex in \(M\). Let \(p_{1},p_{2},...,p_{n}\) be the list of critical points of \(f\), and let \(t_{1},t_{2},...,t_{n}\) be their corresponding critical values.  
We choose \(k\) regular values \(C=\{c_{1},\cdots,c_{k}\}\) of \(f\). These values will be utilized to slice the manifold \(M\) into \(k+1\) submanifolds \(M_{1},..,M_{k+1}\), such that the vertex counts of the submanifolds are approximately equal to each other. We also need to determine the connected components \(f^{-1}(c_{i})\) for \(c_{i}\) in \(C\). The connected components of the regular value \(c_{i}\in C\) can be computed in linear time with respect to the number of edges in \(M\), as follows. We visit all edges of \(M\) and detect if an edge crosses one of the values \(c_{i}\). If such an edge is found at a level \(c_{i}\), then we keep rotating around to find all other edges crossing the value \(c_{i}\) within the same connected component of \(f^{-1}(c_{i})\). After visiting all edges, we have also determined the connected components of \(f^{-1}(c_{i})\) for each \(c_{i}\in C\). We will denote the set of all connected components of \(f^{-1}(c_{i})\) for \(1\leq i\leq k\) by \(\mathcal{C}_{f}\). We also call an edge in \(M\) that crosses \(f^{-1}(c_{i})\) a crossing edge. See Figure 11 for an illustration.
3. Divide the surface \(M\) into \(k+1\) partitions along the level sets \(f^{-1}(c_{i})\) for all \(c_{i}\in C\). We obtain a list of submanifolds \(M_{[c_{0},c_{1}]}\),...,\(M_{[c_{k},c_{k+1}]}\). Here, we set \(c_{0}=t_{1}\) and \(c_{k+1}=t_{n}\). We will denote to \(M_{[c_{i-1},c_{i}]}\) by \(M_{i}\). The set \(\{M_{i}|1\leq i\leq k+1\}\) will be denoted by \(\mathcal{M}_{f}\).
4. Next, we extend \(M_{i}\) by adding other vertices in \(M\) as follows. Let \(E_{i-1}\) and \(E_{i}\) be the edges in \(M\) that intersect with \(f^{-1}(c_{i-1})\) and \(f^{-1}(c_{i})\), respectively. The submanifold \(M_{i}^{\prime}=M_{[c_{i-1},c_{i}]}^{\prime}\) is obtained from \(M_{[c_{i-1},c_{i}]}\) by adding the vertices from \(E_{i-1}\) and \(E_{i}\). We call the edges \(E_{i-1}\) and \(E_{i}\) the boundary edges of \(M_{[c_{i-1},c_{i}]}^{\prime}\). Note that every two consecutive submanifolds from \(\mathcal{M}_{f}\) intersect with each other along their boundary edges. See Figure 12 for an illustration.  
The purpose of extending the submanifolds \(M_{i}\) to \(M_{i}^{\prime}\) in step (3) will be justified in the gluing stage in Section 5.3.  
Figure 11: An illustration of the partition stage. (**a**) A connected component of the submanifold \(M_{i}\) is obtained. (**b**) \(M_{i}\) is extended to \(M_{i}^{\prime}\) by adding the crossing edges. (**c**) A closeup of the crossing edges of the manifold \(M_{i}^{\prime}\). The blue edges represent the crossings edges of \(E_{i-1}\) and the green curve represents the portion of the curve \(f^{-1}(c_{i-1})\) within the closeup region.