Optimal 2-Coverage of a Polygonal Region in a Sensor Network

Abstract

Wireless sensor networks are a relatively new area where technology is developing fast and are used to solve a great diversity of problems that range from museums’ security to wildlife protection. The geometric optimisation problem solved in this paper is aimed at minimising the sensors’ range so that every point on a polygonal region R is within the range of at least two sensors. Moreover, it is also shown how to minimise the sensors’ range to assure the existence of a path within R that stays as close to two sensors as possible.

1. Introduction and Related Work

Problems related to wireless ad-hoc networks (or just sensor networks) have emerged in the last few years as a result of the fast development of the associated technology. These networks have great long-term economic potential and pose many new system-building challenges [1]. Sensor networks are used to solve a great diversity of problems that range from battlefield monitoring to weather detection, museums’ security and even wildlife protection [2]. The problems solved in this paper are related to coverage. Since each sensor, antenna (or any device able to send or receive some sort of signal) can be located anywhere within a specific region, coverage measures the quality of this placement. Let R be a region on the plane that is monitored by a given sensor network. Does this network cover R completely? If not, is it still an acceptable coverage? These questions are obviously fundamental issues in this area. Coverage can be seen from two opposite perspectives. In the worst-case coverage there is an attempt to locate the regions of R that are hidden from the sensors, that is, not monitored. These areas are known as breach regions. On the other hand, the best-case coverage is characterised as an attempt to locate the areas that are are within reach of as many sensors as possible, thus identifying the “best” monitored regions of R. The following optimisation problems aim to tune a sensor network so that a given region is well covered and assure the existence of a path between two points within the region that stays as close to the sensors as possible. In other words, a best-coverage path.

Let $S=\{s_1,s_2,\dots ,s_n\}$ be a set of n points on the plane that represent the location of n devices that are able to send or receive some sort of signal, like antennas. The devices of S are homogeneous in the sense that they all have the same power transmission range $r\in {\mathbb{R}}^{+}$. It is also assumed that they are in general position. Let R be a polygonal region that models a street network (see Figure 1, the background image was taken from Google Maps). People and vehicles can move within R to reach specific locations there.

Figure 1. The blue polygonal region models a street network.

Figure 1. The blue polygonal region models a street network.

In this example, the set S of antennas is located at the buildings’ tops and not on the streets, so no antennas are found on R. However, the algorithms in this paper work for both cases. The regions within reach of at least two antennas are considered to be well covered. Therefore, the larger these regions the better the coverage of R. This restriction is derived by several real-life problems that may occur in situations where stronger monitoring is needed, such as military applications. This is also the case when multiple sensors are required to detect an event.

In Figure 2 and Figure 3 there are two examples of a polygonal region each with a set of homogeneous antennas (represented by black dots) whose coverage area is shown in white. The antennas’ range in Figure 2 is shorter than in Figure 3. The best covered regions, that is, regions that are within reach of at least two antennas are shown in dark blue. In these zones, any traffic would get a signal transmitted from at least two antennas.

Figure 2. The areas of the polygonal region that are covered by at least two antennas are shown in dark blue.

Figure 2. The areas of the polygonal region that are covered by at least two antennas are shown in dark blue.

Figure 3. The areas of the polygonal region that are covered by at least two white antennas are shown in dark blue.

Figure 3. The areas of the polygonal region that are covered by at least two white antennas are shown in dark blue.

As stated before, it can be seen that larger transmission ranges provide better coverage. However, as larger ranges also result in higher costs, it is appropriate to balance one against the other. Moreover, the optimisation of the antennas’ transmission range also improves the life span of wireless-enabled devices [3]. Consequently, the main problem in this paper is to minimise the antennas’ range in order to provide a good coverage of region R and or to assure the existence of a well covered path within R. What follows is therefore a formal definition of the problem. Assuming all distances are Euclidean, 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.

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.

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.

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}(logn)$ time. This diagram can be constructed in $\mathcal{O}(nlogn)$ time, so its construction is only justified when the number of queries regarding S is larger than $logn$. 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, Abellanas et al. [6] and Mehta et al. [7] study routes that are always close (or always far) to a given set of sensors on the plane. Agnetis et al. [8] compute a subset of a given set 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 Meguerdichian’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 Boukerche et al. [2], Li et al. [9] and Mehta et al. [7]. Recently, Zhang 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. Contrary to some of the previous work, their algorithms can be applied to arbitrary topologies of the sensor network. Using variable radii sensors, Zhou et al. [11] address the problem of selecting a minimum energy-cost coverage, where each sensor can vary its sensing and transmission radius. They propose several centralised and distributed algorithms to compute a small subset sensors that are sufficient to cover the region required to be monitored. Das et al. [12] study efficient location of base stations to cover a convex region when the base stations are interior to the region. Making use of Voronoi diagrams, they developed a fast iterative algorithm to solve this problem. In their paper there are also some citations related to the coverage of a square or an equilateral triangle. Also employing Voronoi diagrams, Stoyan and Patsuk [13] consider the problem of covering a compact polygonal set using identical discs of minimum radius. Boukerche et al. [2] address sensor networks by studying how well a large wireless sensor network can be monitored or tracked while keeping a long lifetime. Their solution outperforms previously known techniques. Bezdek and Kuperberg [14] research an intermediate problem between 1-coverage and 2-coverage. They study the minimum coverage of the plane using homogeneous discs so that the region remains covered even when the radius of one of the discs decreases. This concept provides a continuous transition from 1-coverage to 2-coverage.

This paper is organised as follows: in Section 2 it is shown how to minimise the power transmission range of a set S of antennas to 2-cover a polygonal region R (with or without holes). In Section 3, it is introduced an algorithm to minimise the power transmission range that assures the existence of a 2-covered path between two points on R. This problem is solved using the respective decision problem that is also addressed in this section. The cases where region R is not polygonal are discussed in Section 4, which is followed by a brief discussion of the results.

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:

(a)

A vertex of R;

(b)

An intersection point between $B(R)$ and ${\mathrm{VD}}_2(S)$;

(c)

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)$.

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).

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).

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 6. (a) The candidates are represented by squares: vertices of R, points of $B(R)\cap {\mathrm{VD}}_2(S)$ and a vertex of ${\mathrm{VD}}_2(S)$ interior to R. (b) ${\mathrm{MR}}_S(R)={\mathrm{MR}}_S(q)=r$.

Figure 6. (a) The candidates are represented by squares: vertices of R, points of $B(R)\cap {\mathrm{VD}}_2(S)$ and a vertex of ${\mathrm{VD}}_2(S)$ interior to R. (b) ${\mathrm{MR}}_S(R)={\mathrm{MR}}_S(q)=r$.

Algorithm Minimum Range to 2-Cover a Region

Input: Set S of n antennas and polygonal region R

Output: ${\mathrm{MR}}_S(R)$

 1. Compute ${\mathrm{VD}}_2(S)$, the second order Voronoi diagram of S.

 2. Compute the intersection set $I\leftarrow B(R)\cap {\mathrm{VD}}_2(S)$.

 3. Add the vertices of ${\mathrm{VD}}_2(S)$ that are interior to R to set I.

 4. Add the vertices of R to set I.

 5. ${\mathrm{MR}}_S(R)\leftarrow max\{{\mathrm{MR}}_S(q):q\in I\}$.

The following result is a direct consequence of the algorithm Minimum Range to 2-Cover a Region.

Theorem 1

Given a set S of n antennas and a polygonal region R with m vertices, ${\mathrm{MR}}_S(R)$ can be calculated in $\mathcal{O}(mn)$ time and space.

Proof: 

Computing ${\mathrm{VD}}_2(S)$ takes $\mathcal{O}(nlogn)$ time since S is formed by n antennas on the plane [5]. The cardinality of set $I=B(R)\cap {\mathrm{VD}}_2(S)$ is at most $mn$ since ${\mathrm{VD}}_2(S)$ has n faces and R has m edges. Adding all the vertices of ${\mathrm{VD}}_2(S)$ that are interior to R to set I takes $\mathcal{O}(nm)$ time. The region’s vertices can be added to I in $\mathcal{O}(m)$ time. For each intersection point $q\in I$, ${\mathrm{MR}}_S(q)$ is calculated in constant time using ${\mathrm{VD}}_2(S)$ as it is the distance between q and its second closest antenna. The largest of these distances is ${\mathrm{MR}}_S(R)$. Overall, the time complexity of this procedure is $\mathcal{O}(mn)$. Regarding the space complexity, there is the need to store at most $mn$ intersection points while ${\mathrm{VD}}_2(S)$ can be stored in $\mathcal{O}(n)$ space [5]. Consequently, this algorithm runs in $\mathcal{O}(mn)$ time and space.

Corollary 1

Given a set S of n antennas and a convex polygonal region R with m vertices, ${\mathrm{MR}}_S(R)$ can be calculated in $\mathcal{O}(m+nlogn)$ time and $\mathcal{O}(m+n)$ space.

Note that, for a convex polygonal region R, ${\mathrm{MR}}_S(R)$ can be calculated in $\mathcal{O}(m+n)$ time and space if ${\mathrm{VD}}_2(S)$ has been previously built.

3. Minimum Transmission Range to 2-Cover a Path on a Polygonal Region

Given two points p and q on a polygonal region R, the objective of this section is to calculate the minimum transmission range of the antennas such that there is a 2-path on R connecting p and q, $P(p,q)$. In Figure 7(a), the black path connecting p and q is not a 2-path since some of its points are only covered by one antenna. On the other hand, the yellow path in the same figure is a 2-path between p and q. Not only it is 2-covered by S as it exists within R which makes it the interesting type of 2-path for this section. In the following, whenever 2-path is mentioned, it is understood as a 2-path within R.

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.

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.

3.1. 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 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 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.

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 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)$.

Algorithm Preprocess (PRE)

Input: Set S of n antennas, range r, ${\mathrm{VD}}_2(S)$, convex piece $R_i$

Output: Arrangement $A_i$ and graph $G_i$

• Compute the arrangement $A_i$:
  For each ${\mathrm{VR}}_2(s_i,s_j)$ do

  (a)

  Compute $l_r(s_i,s_j)$, the lens resulting from $D(s_i,r)\cap D(s_j,r)$

  (b)

  Compute the face $a_k$ of arrangement $A_i$, which is the region resulting from the non-empty intersection ${\mathrm{VR}}_2(s_i,s_j)\cap l_r(s_i,s_j)\cap R_i$

• Construct graph $G_i$:
  For each face $a_k\in A_i$ do

  (a)

  Add node $n_k$ to $G_i$

  (b)

  For each neighbouring face $a_j\in A_i$ of $a_k$ do

  If $a_k\cap a_j\ne \varnothing$ then add edge $\overline{n_k{n}_j}$ to $G_i$

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}(n{m}_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. Each lens $l_r(s_i,s_j)$ is intersected at most four times by ${\mathrm{VR}}_2(s_i,s_j)$ and $l_r(s_i,s_j)\cap {\mathrm{VR}}_2(s_i,s_j)$ is convex. Consequently, the intersection between that convex region and $R_i$ also is convex and can be found in $\mathcal{O}(m_i+n_i)$ time, $n_i$ being the complexity of ${\mathrm{VR}}_2(s_i,s_j)$. As the Voronoi diagram has amortised linear complexity, the arrangement $A_i$ can be found in $\mathcal{O}(n+n{m}_i)=\mathcal{O}(n{m}_i)$ time. An intersection graph of $A_i$ has n nodes since there is at most one node per Voronoi region that intersects $R_i$ (see Figure 10(a)). Two nodes of $G_i$ are connected if their corresponding faces of $A_i$ intersect. The vertices of each face of $A_i$ can be used to check if it intersects another face of $A_i$. It suffices that each vertex is identified as an apex of a lens, a point on $B(R)$ or a point on a Voronoi edge. The latter is the important type of vertex for this procedure. Suppose face $a_k$ has a vertex v that is a point on a Voronoi edge that separates ${\mathrm{VR}}_2(s_k,s_l)$ from ${\mathrm{VR}}_2(s_l,s_j)$. Then v belongs to lenses $l_r(s_k,s_l)$ and $l_r(s_l,s_j)$, which means faces $a_k$ and $a_j$ intersect each other. Therefore, to construct $G_i$ it suffices to connect the nodes corresponding to the faces of $A_i$ that share at least one vertex on the same Voronoi edge. Overall, this arrangement and corresponding graph can be constructed in $\mathcal{O}(n{m}_i)$ time.

Note that $G_i$ has as many edges as the Voronoi diagram and that it may not be connected (see graph on green region in Figure 10(a) Sec:Conclusions). To decide if a 2-path between points p and q exists, there is the need to unite all the restricted graphs to form the final intersection graphs G of arrangement A. Obviously, a node of $G_i$ is merged with another node of $G_j$ if the faces of A they correspond to intersect each other (see Figure 10). The following algorithm solves the decision problem.

Algorithm Power Transmission Range Test (TRT)

Input: Set S of antennas, range r, ${\mathrm{VD}}_2(S)$, region R, points p and q

Output: YES or NO

• Decompose R in convex pieces by adding a set L of rays.
• For each convex piece $R_i\subseteq R$ do
  $\{A_i,G_i\}\leftarrow$ PRE($S,r,{\mathrm{VD}}_2(S),R_i$).
  $G\leftarrow G\cup G_i$.
  $A\leftarrow A\cup A_i$.
• For every ray $l_i\in L$ do
  $F_i\leftarrow \{a\in A:\text{an}\text{edge}\text{of}\text{face}a\text{is}\text{on}{l}_i\}$.
  Merge the nodes of G whose corresponding faces of $F_i$ lie on the same lens.
• Assign p to node $n_p$ and q to node $n_q$.
• Traverse G starting at p using the DFS algorithm [18].
• If node q is found then return YES. Otherwise return NO.

Figure 10. (a) Three subgraphs corresponding to the three convex pieces, the one in the green region is disconnected. (b) There is not a 2-path between p and q because they lie in different connected components of the complete graph.

Figure 10. (a) Three subgraphs corresponding to the three convex pieces, the one in the green region is disconnected. (b) There is not a 2-path between p and q because they lie in different connected components of the complete graph.

Point p is assigned to node $n_p$ that is the node of G whose corresponding face of A contains p. In a similar way, point q is assigned to node $n_q$. Consequently, the existence of a 2-path connecting p and q depends on $n_p$ and $n_q$ being within the same connected component of G (see Figure 10(b)). The method chosen to traverse G is the Depth-First Search since its complexity is linear on the number of edges of the graph [18].

Theorem 3

Let S be a set of n antennas with transmission range r and R a polygonal region decomposed in convex pieces by adding k rays. Let M be the largest complexity of the convex pieces. Deciding if a 2-path between points p and q exists takes $\mathcal{O}(k\times nM)$ time if ${\mathrm{VD}}_2(S)$ has been previously built.

Proof: 

Decomposing region R with m vertices in convex pieces by adding a set L of k rays takes $\mathcal{O}(m+k^{2}log(\frac{m}{k}))$ time [16]. Consequently, R is decomposed in $k+1$ convex pieces. Supposing each convex piece $R_i$ has $m_i$ vertices, let $M=max\{m_1,\dots ,m_{k+1}\}$. According to Theorem 2, constructing $G_i$ for each convex piece takes $\mathcal{O}(n{m}_i)$ time, so constructing a first version of G takes $\mathcal{O}(k\times nM)$ time. For the same reason, constructing arrangement A also takes $\mathcal{O}(k\times nM)$ time. Studying the vertices of every face of A on a convex piece takes $\mathcal{O}(nM)$ time. Consequently, finding the sets of faces which have an edge on the same ray of L takes $\mathcal{O}(k\times nM)$ time. Computing the lens that contains a face of A can be done in constant time. Every ray of L can intersect n Voronoi regions and so n faces of A. Therefore, each set of faces $F_i$ has cardinality at most n. The vertices of the rays of L can have degree 3 at most [16], so the number of nodes of G to be merged at a time is at most 3, which can be done in constant time. Consequently, the construction of G is concluded in $\mathcal{O}(kn)$ time. Locating p and q on A can be done in $\mathcal{O}(nM)$ time. In the worst case, the Depth-First Search algorithm has to visit every node of G twice [18]. Therefore, traversing G to decide if there is a 2-path between points p and q takes $\mathcal{O}(kn)$ time. Overall, this decision problem can be solved in $\mathcal{O}(k\times nM)$ time.

Note that if R is a convex polygonal region with m vertices, then deciding if a 2-path between points p and q exists takes $\mathcal{O}(nm)$ time if ${\mathrm{VD}}_2(S)$ has been previously built (Theorem 2). It suffices to compute the arrangement and the corresponding graph just for one convex piece.

3.2. 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\ge 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)

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\}$.

(b)

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))$.

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 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.

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 $▵(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))$.

(a)

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)$;

(b)

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}(▵(s_i,s_j,s_k))$.

Figure 12. The antennas’ range is $r={\mathrm{MR}}_S(P(p,q))$ and ${\mathrm{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.

Figure 12. The antennas’ range is $r={\mathrm{MR}}_S(P(p,q))$ and ${\mathrm{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.

Algorithm Minimum Transmission Range

Input: Set S of n antennas, points p and q on region R

Output: ${\mathrm{MR}}_{S,R}(P(p,q))$

• Compute ${\mathrm{VD}}_2(S)$, the second order Voronoi diagram of S.
• Compute set $I\leftarrow \{p,q\}\cup \{B(R)\cap {\mathrm{VD}}_2(S)\}$.
  Add the vertices of R to set I.
• Find set B of candidates for bottleneck-points using Proposition 2.
• $I^{\prime }\leftarrow \{{\mathrm{MR}}_S(x):x\in \{I\cup B\}\}$.
  Calculate $r_0=max\{{\mathrm{MR}}_S(p),{\mathrm{MR}}_S(q)\}$.
• Perform a binary search on $I^{\prime }=\{r_i\in I^{\prime }:r_i\ge r_0\}\cup \{r_0\}$:
  For the median range $r_i\in I^{\prime }$ do
   If TRT($S,{\mathrm{VD}}_2(S),r_i,R,p,q$) = YES

  • Then proceed the search on $I^{\prime }\leftarrow \{r_j\in I^{\prime }:r_j\le r_i\}$.
  • Otherwise proceed the search on $I^{\prime }\leftarrow \{r_j\in I^{\prime }:r_j>r_i\}$.
• The final range is ${\mathrm{MR}}_{S,R}(P(p,q))$.

Figure 12 shows the two types of bottleneck-points and their relation to the second order Voronoi diagram of S. According to Proposition 2, candidates to bottleneck-points are found on the edges of ${\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.

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.

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.

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}(knMlogmn)$ time.

Proof: 

Computing ${\mathrm{VD}}_2(S)$ takes $\mathcal{O}(nlogn)$ 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}(mnlogmn)$ time. Supposing each convex piece has $m_i$ vertices, let $M=max\{m_1,\dots ,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}(knMlogmn)$ time, which is the overall complexity to calculate ${\mathrm{MR}}_{S,R}(P(p,q))$.

4. 2-Covering a Nonpolygonal Region

This work is focused on in the case that the region is a street network, therefore it is modelled by a polygonal region. Nevertheless, this street network can also be modelled by a connected graph that can be seen as a degenerated version of the case presented above. Given a set S of n antennas, calculating the minimum power transmission range to assure the existence of a 2-covered path between two nodes of a street graph $G=(N,E)$ takes $\mathcal{O}(|E|\times n)$ time, assuming $|E|>logn$ [19].

If an user can move within the whole plane (like an airplane flying through the sky), then region R is actually ${\mathbb{R}}^2$. This situation has also been addressed before. Calculating the minimum power transmission range to assure the existence of a 2-covered path between two points on the plane can be done in $\mathcal{O}(nlogn)$ time [15]. This work also shows how to compute a 2-path between two points.

5. Discussion of the Results

This article studies the 2-coverage of a polygonal region R. First it is shown how to completely cover R using a set of n antennas with minimum transmission range and then how to minimise the antennas’ range so that a 2-path between two points exists on R. The first problem is solved using an algorithm that runs in $\mathcal{O}(mn)$ time and space, m being the number of vertices of R. However, this complexity is lowered to $\mathcal{O}(m+nlogn)$ time and $\mathcal{O}(m+n)$ space if the region is convex. With this in mind, the next problem was solved using a decomposition of R in convex pieces. The minimisation of the antennas’ range to assure the existence of a 2-path between two points on R proved to be harder to solve and so the first approach was directed at the decision problem. Therefore, if the antennas’ power transmission range is $r\in {\mathbb{R}}^{+}$ then decide if there is a 2-path between two points on R takes $\mathcal{O}(k\times nM)$ time (k is the number of rays added to decompose R in convex pieces and M the complexity of the convex piece with more vertices). Using the decision algorithm together with a binary search finally solves the main problem in $\mathcal{O}(knMlogmn)$ time. The binary search is performed on a set of ranges which are needed to 2-cover particular points found on R and ${\mathrm{VD}}_2(S)$.

Although it is assumed throughout the paper that the point defining the minimum range to 2-cover a particular object is unique, this is not true in degenerate cases. The antennas’ distribution might result in a scheme where there can be more than one of these points. However, bottleneck-points can be found using the same technique and they still fall into only two types. The classification of bottleneck-points does not change in the presence of degenerate cases.

Although the antennas’ range is optimised to assure the existence of a 2-path on R, it is never shown how to construct such path. Future work obviously passes through explaining how to construct a 2-path between two points and even how to construct the shortest 2-path between those points. It is not clear how to do this efficiently because the space where the 2-path exists has a shape that is uncommon, some edges are arcs, others are line segments.