# Balanced Parallel Exploration of Orthogonal Regions
## 5 Analysis
### Room Scan
#### 5.2.2 Room Exploration  
Let \(R_{1},R_{2},\ldots,R_{r}\) be the sequence of rooms that are visited in the algorithm. For each room \(R_{i}\), let \(D_{i}\) be the maximum shortest path distance between any pair of points in \(R_{i}\), and let \(n_{i}\) be the total number of traversable points in the room. For each room, the total number of previously explored points in the previously explored rooms are taken into account when determining the difference in work between agents. As with perimeter scan, we will use \(D_{\max}=\max_{i}D_{i}\). We will show that when the sum of work in all rooms explored exceeds \(kD_{\max}\), a ratio 8 between the works of the agents is maintained. We define \(N_{i}\) as the sum of all the traversable points in all the rooms up to \(R_{i}\), i.e., \(N_{i}=\sum_{j=1}^{i}n_{j}\). After the completion of the room \(R_{i}\), each agent \(k\) has an associated work \(w_{k}^{i}\). We extend Lemma 10, to the more general case where agents have prior work. **Lemma 11**. : _If before the scan of room \(R_{i}\), \(i>1\), the work of any two agents \(g\) and \(h\) differ in work \(|w_{g}^{i-1}-w_{h}^{i-1}|\leq 4D_{\max}\), then at the end of the room scan of \(R_{i}\) then the difference is maintained or a ratio 8 is achieved._  
**Proof. ** Initially, only one agent gets Active in \(R_{i}\), suppose \(g\). It must be that the work of \(g\) before \(R_{i}\), \(w_{g}^{i-1}\), is at most the work of every other agent \(h\). In its traversal, \(g\) gains at most \(4D_{i}\leq 4D_{\max}\) additional work. Therefore, \(|(w_{g}^{i-1}+4D_{i})-w_{h}^{i-1}|\leq|(w_{g}^{i-1}+4D_{\max})-w_{h}^{i-1}| \leq 4D_{\max}\). Thus, since our algorithm always picks an agent with the lowest work, as long as a single agent is scanning the room \(R_{i}\), the maximum work difference of \(4D_{\max}\) is preserved. Now, that the algorithm sends two or more agents for scanning. The agents that are selected by the Leader to scan the room must start with a ratio of work 4 within each other. These selected agents have also the lowest work at the time of their activation, with respect to all agents \(k\), and each agent must have minimum total work of \(D_{i}\). At any time during their scan, the Active agents accumulate new work, but each agent at most doubles its work (according to our algorithm). Therefore, the ratio of work among those Active agents does not exceed 8. Between Active and Inactive agents, the difference of work is decreasing until the time when Inactive agents get less work than the Active, and the Inactive become Active themselves. Until that happens the difference of work between Active and Inactive is \(4D_{\max}\). After that, the ratio 8 is also maintained between Active and Inactive agents. Even if all agents get Active, then they have a ratio 4 among them when they start scanning and will maintain a ratio 8 upon returning if one becomes Inactive due to the completion of their area. Therefore, in all cases, if multiple agents start scanning either the work difference is bounded by \(4D_{\max}\) or a ratio 8 between the works of the agents is maintained. **Lemma 12**. : _If before the scan of room \(R_{i}\), \(i>1\), the work of any two agents \(g\) and \(h\) have a difference in their ratio of work \(1/8\leq w_{g}^{i-1}/w_{h}^{i-1}\leq 8\), then at the end of the room scan of \(R_{i}\) then ratio 8 is maintained or regress to difference of \(4D_{\max}\)._  
**Proof. ** Similar to the proof of Lemma 11, at the beginning only one agent scans \(R_{i}\), say agent \(g\), which gains at most \(4D_{i}\) work. Any other agent \(h\) must have work \(w_{h}^{i-1}\geq w_{g}^{i-1}\). If \(w_{h}^{i-1}<D_{i}/4\), then, the ratio 8 between these two agents is not preserved, but there is a maximum difference of \(4D_{\max}\) in their works. If more than one agent becomes Active for scanning, then similar to the proof of Lemma 11, the work ratio of 8 is maintained or the difference of works is bounded by \(4D_{\max}\). **Lemma 13**.