## 3 Minimum Transmission Range to \(2\)-Cover a Path on a Polygonal Region
### Decision Problem  
In this subsection, it is proposed an algorithm to solve the following decision problem: given a set \(S\) of \(n\) antennas with power transmission range \(r\in\mathbb{R}^{+}\) and two points \(p\) and \(q\) on \(R\), decide if there is a \(2\)-path connecting \(p\) and \(q\). This algorithm will then be used to solve the main problem. As mentioned before, a \(2\)-path from \(p\) to \(q\) exists if and only if \(p\) and \(q\) lie in the same connected component of the union of lenses (see Figure 7(b)). If it exists, such \(2\)-path only crosses the regions of \(R\) that are \(2\)-covered. With this in mind, let \(A\) be the arrangement of the union of lenses confined to region \(R\) and intersected by \(\mathrm{VD}_{2}(S)\) (see Figure 8). If there is a \(2\)-path between \(p\) and \(q\) on \(R\), then it exists within \(A\). If \(R\) is not convex, then there can be more than one face of \(A\) per Voronoi region. For example, there are two non-connected faces of \(A\) defined by the spikes of \(R\) on the lower leftmost Voronoi region in Figure 8.  
According to Corollary 1, working with convex regions is easier since the number of intersection points decreases sharply. Moreover, there is only one face of \(A\) per Voronoi region. Consequently, the first step to solve this problem is to decompose \(R\) in convex pieces (see Figure 9(a)). It can be easily done using Steiner points: for each reflex vertex \(v_{r}\in R\) extend a ray from \(v_{r}\), which bisects the internal angle of \(R\) at \(v_{r}\), until it reaches \(B(R)\) or a previous ray. It can be shown that if \(R\) has \(k\) reflex vertices, then this set of rays divides \(R\) into \(k+1\) convex pieces. There are some works on the optimisation of the final number of convex pieces, either using Steiner points [16] or diagonals [17]. However, the partition technique used in this paper does not optimise the resulting number of convex pieces. Figure 7: Region \(R\) is shown in blue. (a) The yellow path is a \(2\)-path on \(R\) connecting \(p\) to \(q\) while the black is not. (b) It is not possible to find a \(2\)-path on \(R\) between \(p\) and \(q\) because they lie in different connected component of lenses. The strategy to decide if there is there a \(2\)-path between \(p\) and \(q\) is based on the construction of an intersection graph \(G\) of the arrangement \(A\). Since \(R\) is partitioned in several convex regions, each will be solved separately. According to this, the following algorithm constructs an intersection graph of the arrangement \(A_{i}\) defined by \(A\) restricted to convex piece \(R_{i}\subseteq R\) (see Figure 9(b)). The complete graph \(G\) is later constructed by properly uniting these smaller graphs. Let \(\mathrm{VR}_{2}(s_{i},s_{j})\) be the second order Voronoi region of antennas \(s_{i}\) and \(s_{j}\) and \(l_{r}(s_{i},s_{j})\) the lens resulting from the intersection of discs \(D(s_{i},r)\) and \(D(s_{j},r)\). Figure 8: Polygonal region \(R\) is shown in blue and \(\mathrm{VD}_{2}(S)\) in a dashed line. The arrangement of the union of lenses confined to \(R\) and intersected by \(\mathrm{VD}_{2}(S)\) is shown in dark blue. Figure 9: (a) Polygonal region partitioned in three convex pieces: \(R_{1}\), \(R_{2}\) and \(R_{3}\). (b) The arrangements \(A_{1}\), \(A_{2}\) and \(A_{3}\) are shown in pink, blue and green, respectively. The temporal complexity to construct the restricted arrangement and corresponding graph is given in the following result. **Theorem 2**: _Let \(S\) be a set of \(n\) antennas with transmission range \(r\) and \(R_{i}\) a convex region with \(m_{i}\) vertices. Arrangement \(A_{i}\) and graph \(G_{i}\) can be constructed in \(\mathcal{O}(nm_{i})\) time if \(\mathrm{VD}_{2}(S)\) has been previously built._  
**Proof**: Let \(S\) be a set of \(n\) antennas with range \(r\) and \(R_{i}\) a convex region with \(m_{i}\) vertices.