## 3 Geocasting Based on Local Coverage Areas
### Establishing Local Coverage Areas  
We assume that each node in the wireless sensor network has the ability to obtain an estimate of its position. Whenever a node publishes information, it is augmented with the current position of the node. An overview of the presented approach of establishing coverage areas is depicted in Figure 1. Nodes keep track of coordinates that are explicitly transmitted. Using the received coordinate information, a node creates its local coverage area. By the term _coverage area_, we understand the geographical area in which the sensor nodes are deployed. In this work, the coverage area of a node is represented by a convex hull [27] that envelopes the locations of the node itself and all its descendant nodes in the tree. The convex hull for a set of points is the minimal convex polygon that contains all the points; it is minimal because the convex hull will be contained in any convex polygon that contains the given points. The local coverage area of a node is the convex hull of the subtree rooted at this node (e.g., the subtree rooted at node x is covered by the red convex polygon and the subtree of node y is represented by the green convex polygon in Figure 1). For the distributed construction of convex hulls along the routing tree, each node receives the convex hull information from all its child nodes and merges them together with the addition of the location of the node itself. This procedure constructs a new composite convex hull, which is forwarded further up the tree until it reaches to the sink. The convex hull of the sink covers all the sensor nodes served by this sink as shown in Figure 1 with the blue convex polygon having seven vertices. Let us denote by \(\mathbf{H_{i}}\) the convex hull representing the (local) coverage area of sensor node or sink \(i\). Let \(p_{i}\) be the position of node \(i\) in the wireless sensor network. Initially, \(\mathbf{H_{i}}=\{p_{i}\}\) contains the coordinate of the node \(i\) itself. However, during the update (_i.e._, merging) process described below, the coordinate of the node itself might be removed from \(\mathbf{H_{i}}\). After the update process, \(\mathbf{H_{i}}\) defines a convex hull of \(n\) vertexes over \(\mathbf{C}\), where \(\mathbf{C}\) is a set of coordinates of \(N\) nodes (_i.e._, the descendant nodes and the node \(i\) itself). \(\mathbf{H_{i}}\) covers all \(N\) nodes in \(\mathbf{C}\). The node \(i\) stores the list of vertices of the convex hull of \(\mathbf{H_{i}}\) in counterclockwise order for the computations in convex hull merging algorithm. Let \(|\mathbf{H_{i}}|\) and \(|\mathbf{C}|\) denote the number of elements in the sets \(\mathbf{H_{i}}\) and \(\mathbf{C}\), respectively. Note that \(|\mathbf{H_{i}}|=n\), \(|\mathbf{C}|=N\), and \(|\mathbf{H_{i}}|\leq|\mathbf{C}|\). Apparently, storing a local coverage area represented by a convex hull uses only \(\mathcal{O}(n)\) storage instead of \(\mathcal{O}(N)\) storage. In literature, many methods are described that transform a set of coordinates to a convex hull, e.g., [28]. Typically, these algorithms operate on a set of coordinates and produce a convex hull, but most of them do not consider addition of coordinates once the convex hull has been created. In fact, to construct convex hulls along the routing tree, we need an algorithm which implements a merge function \(\mathcal{CH}(\mathbf{H},\mathbf{C})=\mathbf{H^{\prime}}\), where \(\mathbf{C}\) can be _(i)_ a single coordinate, _(ii)_ a coordinates set or _(iii)_ a coordinates set representing a convex hull, with \(\mathbf{H^{\prime}}\subseteq\mathbf{C}\cup\mathbf{H}\). Figure 1: Example network with coverage area (_i.e._, convex hull stored in the sink) and local convex hulls stored in sensor nodes. The simplest and the most efficient way to achieve merging of two convex hulls (_i.e._, case _(iii)_) is applying the rotating calipers based algorithm [29, 30] locally in each parent node..