# An Efficient Geometric Search Algorithm of Pandemic Boundary Detection
## 3 Materials and Methods
### Full Cooperation/No Errors
#### 3.2.1 An Efficient Local Geometric Algorithm  
One may choose (arbitrarily) either clockwise or counter-clockwise traversals of the boundary. We build up the boundary cell by cell, adding (some of the) rectilinearly adjacent cells that are potential boundary cells. To describe the algorithm, we need to keep track of a compass direction by which we arrived at the current boundary node (North, East, South, and West) and a notion of \"left\" and \"right\"; see Table 1.  
* Starting from the center; Find the furthest potential boundary cell _start_ on the south; Let stack _stack_ = []: Push _start_ to _stack_;
* _stack is not empty AND we have not returned to start_**do** Pop a cell \(c\) from _stack_; Test the 4 neighbors of \(c\) (E, S, W, N);
* _right(c) is a boundary cell_**then** Push right(_c_) to _stack_;
* _end_
* _current_direction(c) is a boundary cell_**then** Push current_direction(_c_) to _stack_;
* _end_
* _left(c) is a boundary cell_**then** Push right(_c_) to _stack_;
* _end_
* Starting from patient 0, find a boundary cell on the south--go south to the last potential boundary cell, testing each cell along the way (and marking it appropriately). This cell, \(c_{0}\), has an infected node to the North of it and no other infected neighbors; furthermore, no cell to the south of \(c_{0}\) is adjacent to any infected cell. * Set the initial direction \(D=\) east, set the current cell \(c=c_{0}\). This means that when one looks in from cell \(c\) facing direction \(D\), the nearby infected nodes are on the left (could \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Direction \(D\)** & **Left (\(D\))** & **Right (\(D\))** & **Current_Direction (\(D\))** \\ \hline North & West & East & North \\ East & North & South & East \\ South & East & West & South \\ West & South & North & West \\ \hline \hline \end{tabular} We now describe an algorithm 1 for a counter-clockwise traversal to discover the boundary:  
\end{table} 
Table 1: Compass directions and “left”, “right”, and “current_direction”. have a common edge or a common vertex). This will be the invariant throughout the algorithm. * Repeat until you return to the original boundary cell \(c_{0}\): Let the current direction be \(D\) and let the current cell be \(c\); the key idea is that we advance to the next boundary node by choosing a potential boundary node on the right, straight ahead, or on the left, in this order of priority:
* If the cell to the \(\operatorname{right}(D)\) of cell \(c\) is a potential boundary cell, add it to boundary, set the direction \(D=\operatorname{right}(D)\) and update \(c\). * Otherwise, if the cell in direction \(D\) from cell \(c\) is a potential boundary cell, add it to boundary, leave \(D\) unchanged, and update the current cell \(c\). * Otherwise, add the cell to the \(\operatorname{left}(D)\) of cell \(c\) to the boundary, set \(D=\operatorname{left}(D)\), and update \(c\). (Note that this new cell must also be a potential boundary cell at this stage.) The nature of the algorithm is entirely geometric and relies on geometric arguments. Obviously, the resulting boundary is rectilinearly connected, and as we traverse this boundary counterclockwise, all the infected cells are to the left and every one of the boundary nodes has at least one infected cell adjacent to it on the left (via edge of vertex). Ergo, all these cells are potential boundary cells. The boundary consists of only uninfected nodes and partitions the nodes into two sets. All infected nodes are in one set and all the nodes in the other set are uninfected. Claim: the boundary exists. Take as a set all nodes that are uninfected and do not belong to the potential boundary for which there is a path from them to the end of the world that only goes through uninfected nodes. Call this set \(W\). The nodes that are not in \(W\) and have a neighbor in \(W\) is the true boundary; call this set \(B\). Note that these must be uninfected since nodes in \(W\) have no infected neighbors.