# Balanced Parallel Exploration of Orthogonal Regions
## 5 Analysis
### Room Scan
#### 5.2.1 First Room Exploration  
Consider the first closed room and suppose that it is of size \(L_{long}\times L_{short}\), where the length of \(L_{long}\) is at least as large as \(L_{short}\). Suppose also that there is a total of \(n\) traversable points in the room. The aspect ratio of the holes in the room is \(a\). Without loss of generality, we will assume that \(L_{long}\) is horizontal, and \(L_{short}\) is vertical. All agents currently have 0 initial work. Before, we proceed with the work analysis, we need bound the longest shortest path in the room, which will be later used to bound the difference on the works of different agents. **Lemma 8**. : _The maximum shortest path between any two points in a room has length \(D=O(aL_{long})\)._  
Proof. : A shortest path between any arbitrary pair of points in the room can be formed by connecting two subpaths \(h\) and \(v\), the first is horizontal of length \(H\), and the second is vertical of length \(V\), to reach the other point. There can be a hole along the two subpaths. This creates key positions in the path \(pos_{0}\), \(pos_{1}\), \(pos_{2}\), and \(pos_{3}\). \(pos_{0}\) is the starting point, and \(pos_{3}\) is the ending point. Assuming horizontal subpath taken first, \(pos_{0}\) and \(pos_{1}\) are the start and end positions, respectively, of \(h\) and \(pos_{2}\) and \(pos_{3}\) are the start and end positions of \(v\). If \(pos_{1}\
eq pos_{2}\) then there is a path around a hole that goes from \(pos_{1}.x\) to \(pos_{2}.x\) and \(pos_{1}.y\) to \(pos_{2}.y\). This hole is only traversed along two dimensions, one horizontal and one vertical, with lengths \(l_{1}\) and \(l_{2}\), respectively. Therefore, \(l_{1}+l_{2}\leq 2L_{long}\). From Lemma 3, \(H\leq(2a+1)L_{long}\) and \(V\leq(2a+1)L_{short}\). Thus, the total length of the path at most \((2a+1)L_{long}+(2a+1)L_{short}+l_{1}+l_{2}\leq(4a+4)L_{long}\). **Lemma 9**. : _In a room with \(n\) points the total work by all agents is \(O(n)\)._Proof. : Let us take the case that there is a single agent with no specific work threshold to returning to the meeting point in the room. From Algorithm 4, the agent takes the original area, moves to the middle of the long dimension and performs a split traversing unexplored positions along this traversal. After exploration \(Area_{0}\), the total room, generates a stack of connected areas \(Area_{1},Area_{2},\ldots,Area_{i}\) such that there is a path of previously explored points on the split that connects each pair of \(Area_{j}\) and \(Area_{j+1}\). When \(Area_{j}\) is popped off it can either make sub areas \(Area_{j_{1}},\ldots,Area_{j_{1}}\) that are connected through the split of \(Area_{j}\) and \(Area_{j_{i}}\) connect to \(Area_{j+1}\) through the previous split or the agent moves to \(Area_{j+1}\) along the split of \(Area_{0}\). Through this recursive process, the agent traverses split positions at most 4 times (down and up both halves). Every point with \(Area_{0}\) will be part a split in one of the recursive steps. Therefore, the whole recursive process is generating \(4n\) total traversals of the total \(Area_{0}\). Now let us add multiple agents that balance their work, but without acting concurrently, i.e., when the work threshold is reached an agent swaps its stack of work with another agent to balance its work. With a threshold, agents are now able to leave and return to an \(Area_{j}\) if they have completed enough work to return to the Leader and another agent returns in their place. From Lemma 8, the threshold \(2D\) newly explored points. In this, \(2D\) newly explored points pays for \(2D\) already explored points when going to the origin and swap the stacks. Since in the worst case an agent may return at most \(n/2D\) times to the origin, the total work with the threshold is at most \(4n+(n/2D)2D\leq 4n+n\leq 5n\). Finally, we view the complete algorithm with multiple agents that can also share the work when the threshold is reached, i.e., the agents perform parallel exploration.