## 3 Minimum Transmission Range to \(2\)-Cover a Path on a Polygonal Region
### Minimising the Antennas' Transmission Range
According to Proposition 2, candidates to bottleneck-points are found on the edges of  
Figure 12: The antennas’ range is \(r=\operatorname{MR}_{S}(P(p,q))\) and \(\operatorname{VD}_{2}(S)\) is shown in a dashed line. (a) Point \(b=b_{S}(p,q)\) is a type I bottleneck-point. (b) Point \(b=b_{S}(p,q)\) is a type II bottleneck-point. \(\mathrm{VD}_{2}(S)\) that are intersected by the line segment joining the two antennas defining such edge and vertices of \(\mathrm{VD}_{2}(S)\) that are interior to the triangle of the antennas responsible for them. To conclude, \(\mathrm{MR}_{S,R}(P(p,q))\) is calculated using a binary search on a list of ranges. Each range of the list is the minimum transmission range needed to \(2\)-cover a candidate and each candidate is either \(p\), \(q\), a vertex of \(R\), a point of \(B(R)\cap\mathrm{VD}_{2}(S)\) or a bottleneck-point. In every step of the binary search, the corresponding range is tested to check if it is large enough to allow a \(2\)-covered path connecting \(p\) and \(q\). The algorithm _Power Transmission Range Test_ (TRT) introduced in the last subsection will be used to this end. If the range is indeed large enough then the search proceeds on the lowest half of the ranges. Otherwise, the search continues on the highest half of the ranges. In Figure 13 there is an example of a \(2\)-path between \(p\) and \(q\) shown in yellow. Any \(2\)-path between these points only exists if the antennas' transmission range is at least \(\mathrm{MR}_{S,R}(P(p,q))=r\). This range is represented by \(r=d(s_{2},b)=d(s_{4},b)\). The union of lenses on \(R\) is shown in light blue and point \(b\) is a type I bottleneck-point for \(2\)-paths between \(p\) and \(q\) on \(R\). Having this algorithm in mind, the following theorem concludes this subject. **Theorem 4**: _Let \(S\) be a set of \(n\) antennas and \(R\) a polygonal region with \(m\) vertices decomposed in convex pieces by adding \(k\) rays. Let \(M\) be the largest complexity of the convex pieces. Given two points \(p\) and \(q\) on \(R\), \(\mathrm{MR}_{S,R}(P(p,q))\) can be calculated in \(\mathcal{O}(knM\log mn)\) time._  
**Proof**: Computing \(\mathrm{VD}_{2}(S)\) takes \(\mathcal{O}(n\log n)\) time since \(S\) is a set of \(n\) antennas on the plane [5]. Set \(I=\{p,q\}\cup\{B(R)\cap\mathrm{VD}_{2}(S)\}\) has cardinality \(mn\) since \(\mathrm{VD}_{2}(S)\) is linear on \(n\) and \(R\) has \(m\) vertices. Adding \(m\) vertices to \(I\) plus the \(n\) candidates to bottleneck-points for \(2\)-paths between \(p\) and \(q\) takes \(\mathcal{O}(m+n)\) time. Therefore, the set \(I\) can be found in \(\mathcal{O}(mn)\) total time. Computing \(\mathrm{MR}_{S}(x)\) for all \(x\in I\) also takes \(\mathcal{O}(mn)\) time, consequently sorting \(I^{\prime}\) in ascending order takes \(\mathcal{O}(mn\log mn)\) time. Supposing each convex piece has \(m_{i}\) vertices, let \(M=\max\{m_{1},\ldots,m_{k+1}\}\). Then according to Theorem 3, each step of the binary search runs in \(\mathcal{O}(k\times nM)\) time. Consequently, the binary search runs in \(\mathcal{O}(knM\log mn)\) time, which is the overall complexity to calculate \(\mathrm{MR}_{S,R}(P(p,q))\). Figure 13: The yellow \(2\)-path between \(p\) and \(q\) on \(R\) only exists if the antennas’ transmission range is at least \(\mathrm{MR}_{S,R}(P(p,q))=r\). The \(2\)-covered regions of \(R\) are shown in light blue.