## 3 Minimum Transmission Range to \(2\)-Cover a Path on a Polygonal Region
### Minimising the Antennas' Transmission Range  
The optimisation algorithm presented in this subsection calculates the minimum power transmission range of \(S\) that assures the existence of a \(2\)-path on \(R\) between \(p\) and \(q\). Such range is denoted by \(\mathrm{MR}_{S,R}(P(p,q))\). Note that, for \(n\geq 2\), this problem always has a solution because, if the range \(r\) is large enough, all discs of radius \(r\) centred at points of \(S\) contain \(R\). In this case, any path connecting \(p\) to \(q\) on \(R\) is a \(2\)-path. Following the idea presented in Section 2., as the range increases, there is the need to locate point \(b\) that is the first intersection between the connected component of lenses containing \(p\) and the one containing \(q\). As before, this point can either be on \(B(R)\) or interior to \(R\). The first case was discussed in Proposition 1 and so \(b\) can be a vertex of \(R\) or an intersection point between \(\mathrm{VD}_{2}(S)\) and \(B(R)\). The second case is more complicated since now there is no need to completely cover \(R\), in fact, all that is needed is that \(p\) and \(q\) lie in the same connected component of lenses (see Figure 11). This intersection point is called a _bottleneck-point_ for \(2\)-paths between \(p\) and \(q\) and it is denoted by \(b_{S}(p,q)\). **Definition 1** ([15]): _Let \(p\) and \(q\) be two points on the plane and \(S\) a set of antennas with range \(r=\mathrm{MR}_{S}(P(p,q))\)._  
* _A point_ \(b=b_{S}(p,q)\) _is a type I bottleneck-point if there is only one antenna_ \(s_{i}\in S\) _such that_ \(b\in\mathrm{int}(D(s_{i},r))\) _and there are two other antennas_ \(s_{j},s_{k}\in S\) _such that_ \(D(s_{j},r)\cap D(s_{k},r)=\{b\}\)2. _A point_ \(b=b_{S}(p,q)\) _is a type II bottleneck-point if there are exactly three antennas_ \(s_{i},s_{j},s_{k}\in S\) _such that_ \(D(s_{i},r)\cap D(s_{j},r)\cap D(s_{k},r)=\{b\}\) _and there is no antenna_ \(s_{l}\in S\) _such that_ \(b\in\mathrm{int}(D(s_{l},r))\)_._  
Without loss of generality, degenerate input data is not considered, so for all purposes, bottleneck-points are regarded as unique for every pair of points. This subject will be further discussed in Section 5.. With this in mind, it is clear that every \(2\)-path between \(p\) and \(q\) has to cross \(b_{S}(p,q)\). Moreover, any bottleneck-point falls into one of these categories, that is, it is either a type I or type II bottleneck-point [15]. According to the last definition, it is easy to see that a type I bottleneck-point for \(2\)-paths between \(p\) and \(q\) is the midpoint of the segment \(\overline{s_{j}s_{k}}\) (see Figure 11(a)). The next proposition explains the relation between bottleneck-points and the second order Voronoi diagram of \(S\). This relation helps to locate bottleneck-points on the referred diagram. Let \(\triangle(s_{i},s_{j},s_{k})\) be the triangle formed by the antennas \(s_{i},s_{j}\) and \(s_{k}\). **Proposition 2** ([15]): _Let \(p\) and \(q\) be two points on the plane and \(S\) a set of antennas with range \(r=\mathrm{MR}_{S}(P(p,q))\)._  
1. _If_ \(b=b_{S}(p,q)\) _is a type I bottleneck-point covered by_ \(s_{i},s_{j},s_{k}\in S\) _and such that_ \(b\in\mathrm{int}(D(s_{i},r))\)_, then_ \(b\) _is the intersection point between_ \(\overline{s_{j}s_{k}}\) _and the second order Voronoi edge that separates_ \(\mathrm{VR}_{2}(s_{i},s_{j})\) _from_ \(\mathrm{VR}_{2}(s_{i},s_{k})\)_;_
2. _If_ \(b=b_{S}(p,q)\) _is a type II bottleneck-point covered by_ \(s_{i},s_{j},s_{k}\in S\)_, then_ \(b\) _is a vertex of_ \(\mathrm{VD}_{2}(S)\) _and_ \(c\in\mathrm{int}(\triangle(s_{i},s_{j},s_{k}))\)_._  
Figure 11: he antennas’ range is \(r=\mathrm{MR}_{S}(P(p,q))\) and a \(2\)-path connecting \(p\) to \(q\) is shown in yellow. (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. Figure 12 shows the two types of bottleneck-points and their relation to the second order Voronoi diagram of \(S\).