# A Distributed Approach to the Evasion Problem
## 2 Materials and Methods
### Previous Algorithm for the Evasion Problem
#### 2.1.2 [PERSON] Algorithm  
In [2], an algorithm, described here as Algorithm 1, was proposed that solves the Evasion problem for mobile sensors with the ability to sense at least bearing and distance to Delaunay neighbors. The algorithm works on the \(\alpha\)-complex (retaining only Delaunay edges that have length at most \(\alpha\)) by tracking the development of faces of the planar graph as sensors move. [PERSON] assumes that the sensor covered region is connected at all times. Since the Delaunay and the \(\alpha\)-complex are both planar graphs, they divide the plane into some set of regions or faces of the graph--empty regions enclosed by a cycle of edges. Each vertex is incident to some number of such regions, each occurring between an edge and the next edge (seen clockwise). [PERSON] algorithm works by tracking these regions, and using an event-driven approach keeping track of where an evader can be excluded. In [PERSON] paper this is accomplished by marking the regions with _True_ or _False_--marking them in effect with the truth value of the statement \"This region could contain an evader\". As shown in the Algorithm Description 1, [PERSON] recognizes four fundamental events in the event-driven algorithm: a Delaunay edge could become short enough to be included in the \(\alpha\)-complex causing one region to split into two regions; a Delaunay edge could become too long to fit in the \(\alpha\)-complex causing two regions to merge into one region; a Delaunay edge flip that swaps one diagonal of a quadrilateral for the other could occur causing two regions to possibly be replaced by two other regions; a triangle in the \(\alpha\)-complex could become small enough that its Voronoi vertex is covered by all three sensors causing that triangle to be marked _False_. ```
0: A collection \(N\) of coordinates \((x_{i},y_{i})\) of sensing nodes with coverage radius \(r\). 0:\(\textit{True}\) if evasion is possible, False otherwise. 1: Calculate the Delaunay graph \(\mathcal{D}\) of the nodes. \(\triangleright\) Initialization. 2: Find the subgraph \(\mathcal{A}\subseteq\mathcal{D}\) with edges shorter than \(2r\). 3: Determine a list of adjacent regions for all nodes \(v\in\mathcal{A}\), 1 region per adjacent pair of neighbors. 4: Label triangular regions where the corresponding Voronoi vertex is within \(r\) of each node _False_, and _True_ otherwise. 5:for timestep \(t\in T\)do\(\triangleright\) Iteration
6: update coordinates \((x_{i},y_{i})\) of the nodes
7: recompute \(\mathcal{D}\) and \(\mathcal{A}\)\(\triangleright\) event-driven updates
8:if Del-\(\alpha\)then\(\triangleright\) Delaunay edge is short enough to join the \(\alpha\)-complex
9: Split the region into two, inheriting the \(\textit{True}/\textit{False}\) label of the original region. 10:if\(\alpha\)-Del then\(\triangleright\)\(\alpha\)-complex edge is too long
11: Merge two regions into one. 12:if both are labeled as False then
13: Label the merged region False. \(\triangleright\) regions are labeled True by default
14:if edge-flip occurs then
15: the two corresponding regions are replaced by two new regions. 16:if both are labeled as False then
17: Label the new regions False. \(\triangleright\) regions are labeled True by default
18:if triangular region has Voronoi vertex within distance \(r\) of each node then
19: Label the region False
20:
21:return\(\bigvee_{R}\text{label}_{R}\) taken over all regions \(R\)\(\triangleright\) if any region is labeled True then evasion is possible
```  
**Algorithm 1** [PERSON] Evasion Detection algorithm. This algorithm was described in [2]. To demonstrate how [PERSON] algorithm marks zones _False_ and _True_, we illustrate in Figure 1 a hypothetical scenario with five security guards equipped with sensors looking for a missing child wearing a tracking bracelet in the middle of a square park. During the timesteps (a)-(c) all the zones formed with Delaunay triangulation among the sensors are _True_. On step (a) none of the sensors are close enough to become actual neighbors (none of the covered areas intersect).