# Balanced Parallel Exploration of Orthogonal Regions
## 5 Analysis
### Room Scan
#### 5.2.2 Room Exploration
: _At the end of scanning room \(R_{i}\) for any two agents it holds that either \(|w_{g}^{i}-w_{h}^{i}|\leq 4D_{\max}\) or \(1/8\leq w_{g}^{i}/w_{h}^{i}\leq 8\)._  
**Proof. ** We will use induction. For the base case, \(i=1\), the claim holds immediately as initially no agent has any work so all are within \(4D_{\max}\) and ratio 8. Suppose the claim holds up to the scanningof room \(R_{i-1}\). By induction hypothesis, for any two agents \(g\) and \(h\), \(|w_{g}^{i-1}-w_{h}^{i-1}|\leq 4D_{\max}\) or \(1/8\leq w_{g}^{i-1}/w_{h}^{i-1}\leq 8\). If \(|w_{g}^{i-1}-w_{h}^{i-1}|\leq 4D_{\max}\), then from Lemma 11, at the end of the scanning of \(R_{i}\) the difference of the works between two agents is either bounded \(4D_{\max}\) or the ratio of their works is at most 8. Similarly, if \(1/8\leq w_{g}^{i-1}/w_{h}^{i-1}\leq 8\), then from Lemma 12, the work difference is bounded by \(4D_{\max}\) or the ratio of their works is at most 8. Therefore, in all cases it holds \(|w_{g}^{i}-w_{h}^{i}|\leq 4D_{\max}\) or \(1/8\leq w_{g}^{i}/w_{h}^{i}\leq 8\), as needed. Lemma 14 (Room Work): _Upon the completion of each room \(N_{i}\) the total work done up to that point is \(O(N_{i})\)._  
Proof. : From above, \(N_{i}=\sum_{j=1}^{i}n_{j}\), and from Lemma 9, the work done in a room is \(O(n_{j})\), more specifically at most \(6n\). The sum of work for all rooms becomes at most \(6n_{1}+6n_{2}+\ldots+6n_{i}=6N_{i}\) which is \(O(N_{i})\). Lemma 15: _Each agent performs \(O(N_{i}/k)\) work when \(N_{i}\geq 2D_{\max}k\)._  
Proof. : From Lemma 14 the total work from all the agents combined is \(O(N_{i})\), say \(c_{1}N_{i}\) for some constant \(c_{1}\). Therefore, some agent has performed work at most \(c_{1}N_{i}/k\). From Lemma 13, for any two agents \(g\) and \(h\) we have, \(|w_{g}^{j}-w_{h}^{j}|\leq 4D_{\max}\) or \(1/8\leq w_{g}^{i}/w_{h}^{i}\leq 8\). Suppose that \(g\) has the maximum total work, and \(h\) has the minimum total work, among all \(k\) agents. If \(|w_{g}^{i}-w_{h}^{i}|\leq 4D_{\max}\), then agent has \(g\) has no more work than \(c_{1}N_{i}/k+4D_{\max}\leq c_{1}N_{i}/k+2N_{i}/k=O(N_{i}/k)\). If \(1/8\leq w_{g}^{i}/w_{h}^{i}\leq 8\), then agent \(g\) has no more work than \(8c_{1}N_{i}/k=O(N_{i}/k)\). Hence, in any case each agent's work is \(O(N_{i}/k)\). To perform analysis of the time complexity of room scan, we examine the total time given the orthogonal area contains no holes. (Logarithms are base 2.) Lemma 16 (Room Time): _Assuming no holes, upon the completion of each room \(R_{i}\) the maximum total time up to that point is \(\sum_{i=1}^{r}((6n_{i}-4D_{i}\log k)/(k-1)+4D_{i}\log k)+4D_{\max}k\)._  
Proof. : At the start of room scan, we have an initial swapping of work until every agent reach \(4D_{\max}\) work, creating a total time of at most \(4D_{\max}k\) for each agent to swap to be Active. After this point, at the beginning of each room, as we perform slow start, the agents share work doubling the number of Active agents each \(4D_{i}\) time steps taking a total of \(4D_{i}\log k\) time for all agents to become Active. As there are no holes, the algorithm generates rectangular areas initially and all agents get an equal portion of the area. Now that all agents are Active, and given that the work performed in a room is \(6n_{i}\) (Lemma 9) we subtract the amount of work that has been performed during the sharing process and divide by the number of Active agents, \(k-1\) as one agent is Leader, achieving the maximum total time for room completion \(\sum_{i=1}^{r}((6n_{i}-4D_{i}\log k)/(k-1)+4D_{i}\log k)+4D_{\max}k\).