## 2 Minimum Transmission Range to \(2\)-Cover a Polygonal Region  
Let \(R\) be a polygonal region (with or without holes) and \(S\) a set of antennas with the same power transmission range. The boundary of \(R\), denoted by \(B(R)\), is considered to be part of the region \(R\). Region \(R\) is said to be \(2\)-covered by \(S\) if every point on \(R\) is \(2\)-covered. The algorithm introduced in this section calculates the minimum power transmission range of \(S\) to \(2\)-cover \(R\), \(\mathrm{MR}_{S}(R)\). Such range is calculated as being the largest distance between a point \(q\in R\) and its second closest antenna. Let the antennas' range be large enough to \(2\)-cover \(R\). Now suppose this range is reduced until there is just one point \(q\in R\) that is no longer \(2\)-covered. The antennas' minimum range to \(2\)-cover \(q\) is exactly \(\mathrm{MR}_{S}(R)\). The following proposition characterises the location of point \(q\) on \(R\). **Proposition 1**: _Let \(R\) be a polygonal region, \(q\) a point on \(R\) and \(S\) a set of antennas. If \(\mathrm{MR}_{S}(R)=d(q,s_{i})\) for some antenna \(s_{i}\in S\), then \(q\) can only be one of the following:_1. _A vertex of_ \(R\)_;_
2. _An intersection point between_ \(B(R)\) _and_ \(\mathrm{VD}_{2}(S)\)_;_
3. _A vertex of_ \(\mathrm{VD}_{2}(S)\) _interior to_ \(R\)_._  
Proof. : Let \(q\in R\) be such that \(\mathrm{MR}_{S}(R)=d(q,s_{i})\) for some antenna \(s_{i}\in S\). Given an edge \(e\) of \(R\), it is easy to see that \(\mathrm{MR}_{S}(e)\) is calculated using the intersection points between \(e\) and \(\mathrm{VD}_{2}(S)\) plus the endpoints of \(e\). The minimum range of \(S\) that \(2\)-covers all these points is exactly the minimum transmission range needed to \(2\)-cover \(e\) (see Figure 5(a)). Consequently, if \(q\in B(R)\) then \(q\) must be a vertex of \(R\) or an intersection point between \(B(R)\) and \(\mathrm{VD}_{2}(S)\). If \(q\) is an interior point then the situation gets trickier since it does not depend on the shape of \(R\) but on the way lenses interact with each other. As the antennas' range increases, the lenses grow larger and fill the interior of \(R\). The last interior point to be \(2\)-covered must be a point lying in the last \"hole\" (meaning a region of \(R\) not yet \(2\)-covered). These holes are filled when three lenses intersect at a time since not only the intersection point is \(2\)-covered but also its whole neighbourhood (see Figure 5(b)). Since three lenses intersect at a vertex of \(\mathrm{VD}_{2}(S)\)[15], if \(q\) is interior to \(R\) then it has to be a vertex of \(\mathrm{VD}_{2}(S)\). According to this proposition, there are several candidates on \(R\) to be the point needing the largest range in order to be \(2\)-covered. Since every point on \(R\) has to be \(2\)-covered, \(\mathrm{MR}_{S}(R)\) is calculated as the minimum range to \(2\)-cover every such candidate. Therefore, there is the need to analyse every vertex of \(R\), intersection points between \(B(R)\) and \(\mathrm{VD}_{2}(S)\) and vertices of \(\mathrm{VD}_{2}(S)\) interior to \(R\) (see Figure 6(a)). In Figure 6(b) there is an example of a \(2\)-covered polygonal region \(R\) with minimum power transmission range. The point of \(R\) defining \(\mathrm{MR}_{S}(R)\) is \(q\in B(R)\) and so \(R\) is \(2\)-covered if the antennas' transmission range is at least \(\mathrm{MR}_{S}(R)=d(q,s_{4})=d(q,s_{9})\). The following algorithm calculates \(\mathrm{MR}_{S}(R)\). Figure 5: (a) Line segment \(e\) is \(2\)-covered with minimum range \(\mathrm{MR}_{S}(e)=r\). (b) Point \(q\) is the last point to be \(2\)-covered on \(R\). It is a vertex of \(\mathrm{VD}_{2}(S)\) (shown in a dashed line). The following result is a direct consequence of the algorithm _Minimum Range to \(2\)-Cover a Region_.