## 3 Minimum Transmission Range to \(2\)-Cover a Path on a Polygonal Region
### Decision Problem
Each lens \(l_{r}(s_{i},s_{j})\) is intersected at most four times by \(\mathrm{VR}_{2}(s_{i},s_{j})\) and \(l_{r}(s_{i},s_{j})\cap\mathrm{VR}_{2}(s_{i},s_{j})\) is convex. Consequently, the intersection between that convex region and \(R_{i}\) also is convex and can be found in \(\mathcal{O}(m_{i}+n_{i})\) time, \(n_{i}\) being the complexity of \(\mathrm{VR}_{2}(s_{i},s_{j})\). As the Voronoi diagram has amortised linear complexity, the arrangement \(A_{i}\) can be found in \(\mathcal{O}(n+nm_{i})=\mathcal{O}(nm_{i})\) time. An intersection graph of \(A_{i}\) has \(n\) nodes since there is at most one node per Voronoi region that intersects \(R_{i}\) (see Figure 10(a)). Two nodes of \(G_{i}\) are connected if their corresponding faces of \(A_{i}\) intersect. The vertices of each face of \(A_{i}\) can be used to check if it intersects another face of \(A_{i}\). It suffices that each vertex is identified as an apex of a lens, a point on \(B(R)\) or a point on a Voronoi edge. The latter is the important type of vertex for this procedure. Suppose face \(a_{k}\) has a vertex \(v\) that is a point on a Voronoi edge that separates \(\mathrm{VR}_{2}(s_{k},s_{l})\) from \(\mathrm{VR}_{2}(s_{l},s_{j})\). Then \(v\) belongs to lenses \(l_{r}(s_{k},s_{l})\) and \(l_{r}(s_{l},s_{j})\), which means faces \(a_{k}\) and \(a_{j}\) intersect each other. Therefore, to construct \(G_{i}\) it suffices to connect the nodes corresponding to the faces of \(A_{i}\) that share at least one vertex on the same Voronoi edge. Overall, this arrangement and corresponding graph can be constructed in \(\mathcal{O}(nm_{i})\) time. Note that \(G_{i}\) has as many edges as the Voronoi diagram and that it may not be connected (see graph on green region in Figure 10(a) Sec:Conclusions). To decide if a \(2\)-path between points \(p\) and \(q\) exists,there is the need to unite all the restricted graphs to form the final intersection graphs \(G\) of arrangement \(A\). Obviously, a node of \(G_{i}\) is merged with another node of \(G_{j}\) if the faces of \(A\) they correspond to intersect each other (see Figure 10). The following algorithm solves the decision problem. Algorithm **Power Transmission Range Test (TRT)**  
Input: Set \(S\) of antennas, range \(r\), \(\mathrm{VD}_{2}(S)\), region \(R\), points \(p\) and \(q\)  
Output: YES or NO  
1. Decompose \(R\) in convex pieces by adding a set \(L\) of rays. 2. For each convex piece \(R_{i}\subseteq R\) do \(\{A_{i},G_{i}\}\leftarrow\text{PRE}(S,r,\mathrm{VD}_{2}(S),R_{i})\). \(G\gets G\cup G_{i}\). \(A\gets A\cup A_{i}\). 3. For every ray \(l_{i}\in L\) do \(F_{i}\leftarrow\{a\in A:\text{an edge of face $a$ is on $l_{i}$}\}\). Merge the nodes of \(G\) whose corresponding faces of \(F_{i}\) lie on the same lens. 4. Assign \(p\) to node \(n_{p}\) and \(q\) to node \(n_{q}\). 5. Traverse \(G\) starting at \(p\) using the DFS algorithm [18]. 6. If node \(q\) is found then return YES. Otherwise return NO. Point \(p\) is assigned to node \(n_{p}\) that is the node of \(G\) whose corresponding face of \(A\) contains \(p\). In a similar way, point \(q\) is assigned to node \(n_{q}\). Consequently, the existence of a \(2\)-path connecting \(p\) and \(q\) depends on \(n_{p}\) and \(n_{q}\) being within the same connected component of \(G\) (see Figure 10(b)). The method  
Figure 10: (a) Three subgraphs corresponding to the three convex pieces, the one in the green region is disconnected. (b) There is not a \(2\)-path between \(p\) and \(q\) because they lie in different connected components of the complete graph. chosen to traverse \(G\) is the Depth-First Search since its complexity is linear on the number of edges of the graph [18]. **Theorem 3**: _Let \(S\) be a set of \(n\) antennas with transmission range \(r\) and \(R\) a polygonal region decomposed in convex pieces by adding \(k\) rays. Let \(M\) be the largest complexity of the convex pieces.