# Fully Parallel Homological Region Adjacency Graph via Frontier Recognition
## 5 Parallel Algorithm for Computing the _HomDuRAG_  
The entire process is schematically shown in the block diagram in Figure 6. The first two steps have been detailed in Section 3, where the associated \(ACC\) is initialized, for the later computation of jump distances between 0-cells. Having computed 0-cell types according to Figure 4, as well as the jump distances to each adjacent 0-cell (Steps 1, 2, 3 of Algorithm 1), distances from every cell to the two crosses where its frontier ends can be computed in a fully parallel manner. The core of the algorithm is represented in Figure 7, and the regular situation proceeds as follows. At each iteration (Steps 4 and 5 of Algorithm 1), any cell keeps the jump distances towards the two directions  
Figure 5: (**Left**): homological information representative cells of the image in Figure 1 (uppercase, lowercase letters and numbers are 2-, 1- and 0-cells, respectively). (**Center**): homological information in the form of adjacencies among crosses and frontier holes expressed as a _HomDuRAG_ graph. (**Right**): homological information in the form of adjacencies among regions (including adjacencies for region holes) of the same image, meaning the _HomRAG_. Figure 6: Complete pipeline of the algorithm to compute the _HomDuRAG_. The detailed description of the whole process is depicted in Algorithm 1.  
of the frontier, called \(Ja\) and \(Jb\). Each 0-cell asks the cells pointed out by these jumps \(Ja\) and \(Jb\) which distances they hold (\(Ja_{neigh}\) at Step 4.b of Algorithm 1 and \(Jb_{neigh}\) at Step 4.d). If the distance \(Ja_{neigh}\) does not fall into a cross (which always maintains zero values for jump distances), the current 0-cell adds these neighbor values in two separate variables (Figure 7, left): \(Ja_{next}=Ja_{neigh}+Ja(c)\), and \(Ja_{next-other}=Jb(c+Ja(c))+Ja(c)\) (Step 4.c of Algorithm 1). Then, the cell must choose the non-null between \(Ja_{next}\) and \(Ja_{next-other}\). Thus, \(Ja_{next}\) or \(Ja_{next-other}\) are stored in the 0-cell (Steps 4.c.ii or 4.c.iii of Algorithm 1). This would continue until the cell reaches a cross; thus, no further computation is needed (Figure 7, center). This last condition supposes a stop condition in the loop iteration for this 0-cell. It is worth noting the necessary condition to ensure that the jump distances are continuously increasing towards the correct direction (Steps 4.c.ii or 4.c.iii of Algorithm 1). Because it is impossible to know which direction each \(Ja\) and \(Jb\) are holding, the results for \(Ja_{next}\) and \(Ja_{next-other}\) may yield to a null value if the taken \(Ja_{neigh}\) (or \(Jb_{neigh}\) ) goes towards the opposite direction to the initial \(Ja\) (or \(Jb\)). In this case, the sum \(Ja_{next}\) (or \(Ja_{next-other}\)) would be null, and the opposite value, \(Ja_{next-other}\) (or \(Ja_{next}\)), is the one that must be stored in the 0-cell. For the other direction, a similar procedure must be performed (Step 4.d of Algorithm 1). As is usual in synchronous cellular automaton algorithms, two pairs of matrices must always be kept: the current ones (\(Ja\), \(Jb\)) and the newest values (\(Ja_{neu}\), \(Jb_{neu}\)). So, any cell can compute its next jumps as a function of the previous state. Correspondingly, before proceeding with the next loop iteration (Step 4.e of Algorithm 1), the roles of these two pairs are interchanged. A special case is needed to detect cycles in frontiers, such as that of the external frontier of region X in Figure 2. In cycles, the increasing operations of the previous loop would never stop because cycles present no crosses. Labeled 0-cells can be used to detect if jump distances are cycling around; when a 0-cell label (L1a in Figure 7, right) matches that of one of its pointed 0-cells (for example, L2 in the same figure), this means that the increasing operations have completely rounded a frontier, and, consequently, the procedure must stop.