# 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
Claim (a): this must be a rectilinear set; (b): these must be potential boundary; and (c): the set \(B\) is rectilinearly connected. Every node on the boundary is adjacent to exactly two nodes. Non-Geometric Algorithms  
We now describe a different class of algorithms for finding the boundary, where we perform a full adjacency search of the rectilinearly aligned boundary cells. Such an algorithm is useful when there are non-cooperating nodes and the definition of the boundary is adjusted accordingly. In the context of full cooperation, both algorithms are better than brute force contact tracing, and the full adjacency search is obviously more expensive (in terms of number of tests) than the geometric local algorithm of Section 3.2.1. The description of the full search is as follows:  
* This is exactly as before. Starting from patient 0, find a boundary cell \(c_{0}\) to the south. This is done by moving south until the last potential boundary cell \(c_{0}\) is found, testing each cell and its east and west neighbors along the way. The cell \(c_{0}\) has an infected node to the North of it and no other infected neighbors. Moreover, all cells directly south of \(c_{0}\) are uninfected, and all of their east-west neighbors are uninfected. Therefore, by definition, none of the cells on the path from \(c_{0}\) south to the end of the world are potential boundary nodes. * Now consider a graph \(G\) whose vertex set \(V\) consists of uninfected potential boundary cells, and where there is an edge between two cells in \(V\) if they are north-south or east-west neighbors. Note that \(c_{0}\in V\) and \(c_{0}\) is a true boundary node. Our boundary tracing algorithm is now simple: we perform a search on \(G\), starting at \(c_{0}\), stopping as soon as we find a closed path containing \(c_{0}\) and enclosing \(c_{0}\)'s infected neighbor to the north. Note that whenever a neighbor of a cell is explored during such a search, if it or any of its neighbors are not yet tested, a test is performed on individuals therein. As soon as an infected individual is discovered inside a cell, that cell is classified as infected and no further tests are conducted on individuals in that cell. The potential boundary nodes form a connected graph. The algorithm just described is correct. Proof. : By definition, the set of output nodes are connected by rectilinear paths. Therefore, to verify correctness, we just need to check that the connected component of the graph \(G\) containing \(c_{0}\) contains the true boundary. By construction, \(c_{0}\) is on the true boundary. To see this, observe that the set of infected cells is a connected set in the original graph, where two cells are neighbors if they share a vertex or an edge in the \(n\times n\) grid. This is because there is a path of infection back to patient 0. Now consider any potential boundary cell. For (b), by definition, the set of cells output encloses a region that contains the infected neighbor of \(c\) to its north, northwest or northeast. This is because the cells' output cannot contain any of the cells on the line going south from \(c\) Therefore, there are infected nodes inside the rectilinear boundary. However, this implies that all infected nodes are enclosed by this set since there is no way for the infection to pass through the rectilinear boundary and the infected set is connected. When Some Individuals Are Non-Cooperative  
In this case, we treat each \(t\times t\) square of cells as a \"supercell\", thereby creating an \(n/t\) by \(n/t\) size grid. The parameter \(t\) is selected so that in each supercell there will be some cooperative individuals with very high probability. On the other hand, we want to have \(t\) be as small as possible to reduce the number of tests and to get a finer-grain picture of the infection and its boundary. For our experiments, a value of \(t=7\) appears to be a good tradeoff choice. When we test individuals in a super cell, we now compute the fraction \(\alpha\) of infected individuals out of the cooperative ones.