## 1 Introduction and Related Work
Figure 2: The areas of the polygonal region that are covered by at least two antennas are shown in dark blue. the distance between a point \(q\) on the plane and a set \(S\) of points is defined as the minimum distance between \(q\) and any one point of \(S\). Point \(q\) is said to be _covered_ by a set \(S\) of antennas with power transmission range \(r\) if the distance between \(q\) and \(S\) is less or equal to \(r\). Therefore, the antennas' minimum transmission range that covers \(q\) is the distance between \(q\) and \(S\). A point covered by two or more antennas of \(S\) is said to be \(2\)_-covered_ by \(S\) (see Figure 4(a)). This definition aims towards quality coverage, as previously explained. The minimum power transmission range of \(S\) that \(2\)-covers an object \(x\) is denoted by \(\mathrm{MR}_{S}(x)\). For example, if the object is a point \(q\), \(\mathrm{MR}_{S}(q)\) is the minimum power transmission range of \(S\) that \(2\)-covers \(q\). Let \(D=\{D(s_{i},r):s_{i}\in S\}\) be the set of discs of radius \(r\) each centred at an antenna of \(S\). Each nonempty intersection between two discs of \(D\) is called a _lens_ (see Figure 4(b)). The union of these lenses encloses all the points on the plane that are \(2\)-covered by \(S\), thus defining \(2\)_-covered regions_ (see Figure 4(c)). Every point within such regions clearly is \(2\)-covered. The problems presented in the next sections aim to \(2\)-cover a given region while minimising the antennas' range \(r\). Note that the minimum range of the antennas that covers a point can be easily calculated in \(\mathcal{O}(n)\) time since such range is given by the distance between the point and its closest antenna. However, the Voronoi diagram of \(S\)[4] is a useful geometric structure that answers each query in \(\mathcal{O}(\log n)\) time. This diagram can be constructed in \(\mathcal{O}(n\log n)\) time, so its construction is only justified when the number of queries regarding \(S\) is larger than \(\log n\). The two closest antennas to a given point can be found using the second order Voronoi diagram of \(S\), denoted by \(\mathrm{VD}_{2}(S)\). The second order Voronoi diagram of \(S\) divides the plane into several regions by grouping points that share the same two closest antennas [4]. It has the same complexity as the ordinary Voronoi diagram [5]. This diagram is naturally related to the optimisation problems studied in this paper since a point is \(2\)-covered if it is within range of its two closest antennas. Following the previous terminology, there are several works related to geometric optimisation using \(1\)-coverage. For example, [PERSON] _et al._[6] and [PERSON] _et al._[7] study routes that are always close (or always far) to a given set of sensors on the plane. [PERSON] _et al._[8] compute a subset of a given set  
Figure 4: Set \(S\) is represented by dots. (a) Point \(q_{1}\) is covered by antenna \(s_{2}\) with minimum range \(r_{1}=d(s_{2},q_{1})\). Point \(q_{2}\) is \(2\)-covered by \(S\) with minimum range \(r_{2}=d(s_{3},q_{2})\). (b) The lens formed by \(D(s_{1},r)\) and \(D(s_{2},r)\) is shown in dark purple. (c) Regions \(2\)-covered by \(S\) with range \(r\) are shown in dark purple. Point \(q_{1}\) is \(2\)-covered by \(S\), whilst \(q_{2}\) is not. of discs with variable radii whose costs depend on their radii, as well as the same subset but with fixed costs to cover a given line segment at minimum cost. After [PERSON]'s work [1], others followed either by studying different versions of the coverage problem or by improving and proving previous results as are the cases of [PERSON] _et al._[2], [PERSON] _et al._[9] and [PERSON] _et al._[7]. Recently, [PERSON] _et al._[10] developed two localised algorithms to identify whether a sensor is on the boundary of the area covered by a sensor network. In this work, one of the proposed algorithms is based on a technique called the localised Voronoi diagram and the other on neighbour embracing polygons.