# Balanced Parallel Exploration of Orthogonal Regions
## 5 Analysis
### Perimeter Scan
#### 5.1.4 Conversion to Tree  
Given \(Q_{i}\) is a sequence of steps \(q_{i}\) that discovers a room \(i+1\), traversing the discovery of rooms in reverse, \(Q_{r},Q_{r-1},\ldots,Q_{1},Q_{0}\), a tree \(T\) of rooms can be generated (see Figure 6b). The root of \(T\) is room \(R_{r}\) (room \(R_{3}\) in Figure 6) which is the last room to be discovered and corresponds to the room where the agents started the whole discovery process. Suppose that \(R_{r}\) corresponds to sequence \(q_{1},\ldots,q_{l}\) in \(Q_{r-1}\). Room \(R_{r-1}\) was generated from \(Q_{r-2}\) and is included in \(q_{1},\ldots,q_{l}\). The children of \(R_{i}\) are the rooms \(R_{h}\) such that \(R_{h}\) is in the sequence of \(R_{i}\) in \(Q_{i-1}\) between the points \(q_{i}\) and \(q_{i+j}\) that generated \(R_{i}\) (see Figure 6c). Given multiple children of \(R_{i}\) they are added to the tree from left to right following their ordering in the sequence. If a room \(R_{h}\) does not have any room \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Figure 5a** & **Figure 5b** \\ \hline \multirow{4}{*}{\(q^{\prime}_{i}\)} & \(q^{\prime}_{i}.e_{y}=q_{i+j}.e_{y}-1\) & \(q^{\prime}_{i}.e_{y}=q_{i+j}.e_{y}-1\) \\  & \(q^{\prime}_{i}.e_{y}=q_{i+j}.e_{y}\) & \(q^{\prime}_{i}.s_{y}=q_{i-1}.s_{y}\) \\  & \(q^{\prime}_{i}.s_{x}=q_{i+j}.s_{x}\) & \(q^{\prime}_{i}.s_{x}=q_{i-1}.s_{x}\) \\  & \(q^{\prime}_{i}.e_{x}=q_{i-1}.e_{x}\) \\ \hline \multirow{4}{*}{\(q^{\prime}_{i+1}\)} & \(q^{\prime}_{i}.x=q_{i+j}.e_{x}\) & \(q^{\prime}_{i}.x=q_{i+j}.e_{x}\) \\  & \(q^{\prime}_{i}.y=q_{i+j}.e_{y}-1\) & \(q^{\prime}_{i}.y=q_{i+j}.e_{y}-1\) \\ \hline \multirow{4}{*}{\(q^{\prime}_{i+2}\)} & \(q^{\prime}_{i}.s_{y}=q_{i+j}.e_{y}-1\) & \(q^{\prime}_{i}.s_{y}=q_{i+j}.e_{y}-1\) \\  & \(q^{\prime}_{i}.e_{y}=q_{i+j}.s_{y}-1\) & \(q^{\prime}_{i}.e_{y}=q_{i+j+1}.s_{y}\) \\ \cline{1-1}  & \(q^{\prime}_{i}.s_{x}=q_{i+j}.e_{x}\) & \(q^{\prime}_{i}.s_{x}=q_{i+j}.e_{x}\) \\ \cline{1-1}  & \(q^{\prime}_{i}.s_{x}=q_{i+j}.e_{x}\) & \(q^{\prime}_{i}.e_{x}=q_{i+j+1}.e_{x}\) \\ \hline \multirow{2}{*}{\(q^{\prime}_{i+3}\)} & \(q^{\prime}_{i}.x=q_{i+j}.s_{x}\) & \multirow{2}{*}{\(q^{\prime}_{i}.y=q_{i+j}.s_{y}-1\)} \\  & \(q^{\prime}_{i}.y=q_{i+j}.s_{y}-1\) & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Basic Possible Values of \(q^{\prime}\). Figure 5: Two Basic Transformations After Room Scan. (**a**) Sequence after closure when starting with a Wall; (**b**) Sequence after closure when starting with a Corner. Figure 6: Conversion from Rooms to Tree Structure. (**a**) Sequence of room traversals; (**b**) Converting area to visualize as tree structure; (**c**) Changing sequence of points as rooms are discovered through traversal. sequence between its respective \(q_{i}\) and \(q_{i+j}\), then it is considered to be a leaf of the tree. Following these rules we generate a tree structure, with \(R_{r}\) as the root, as we work backwards from the room discovery, Figure 6c, adding the respective children of each room as it is expanded from \(Q_{i}\) to \(Q_{i-1}\) until we return to \(Q_{0}\). For the discussion below assume that two points \(q_{i}\) and \(q_{j}\) are ordered as \(q_{i}<q_{j}\) if \(i<j\), and \(q_{i}=q_{j}\) if \(i=j\). Consider two rooms \(R_{p}\) and \(R_{t}\) that in \(Q_{0}\) have the corresponding subsequences \(q_{i_{0}p},\ldots,q_{i_{0}p+j_{0}p}\) and \(q_{i_{0}},\ldots,q_{i_{0}r+j_{0}r}\) respectively. The sequences of \(R_{p}\) and \(R_{t}\) in \(Q_{0}\) are either _disjoined_, when \(q_{i_{0}p}>q_{i_{0}+j_{0}r}\) or \(q_{i_{0}p+j_{0}r}<q_{i_{0}}\), or _contained_, when \(q_{i_{0}p}>q_{i_{0}r}\) and \(q_{i_{0}+j_{0}r}<q_{i_{0}+j_{0}r}\) or \(q_{i_{0}r}>q_{i_{0}p}\) and \(q_{i_{0}+j_{0}r}<q_{i_{0}r+j_{0}r}\), or _connected_, when \(q_{i_{0}p}=q_{i_{0}r+j_{0}r}\) or \(q_{i_{0}r}=q_{i_{0}p+j_{0}p}\). Lemma 1: _Any pair of connected rooms, with neither being the root, have the same parent._  
Proof: Let us assume that \(R_{p}\) and \(R_{u}\) are two connected rooms. Let \(R_{t}\) be the parent \(R_{p}\).