## 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},\ldots,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. 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 Figures 2 and 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 1: The blue polygonal region models a street network. 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,  
Figure 3: The areas of the polygonal region that are covered by at least two white antennas are shown in dark blue.