The relevance of alpha-hulls to the boundary detection problem in sensor networks

Intuitively, many wireless and sensing applications benefit from knowledge of network boundaries. Many virtual coordinate constructions rely on the farthest set of nodes as beacons. Network edges may also bound routing holes in the network or regions of failure due to environmental effects, or they may indicate the need for additional deployment. Solutions that are both manageable and accurate remain elusive, in part due to the challenge of finding localized solutions. In this paper the potential to solve the edge detection problem using a geometric structure called the alpha-shape (-shape) is explored. For a disc of radius 1=, the -shape consists of nodes (and joining edges) that sit on the boundary of the discs that contain no other nodes in the network. In addition to geometry-related fields of study such as graphics and computational geometry, -shapes have been used in disciplines such as molecular biology and particle physics. The relationship between the -parameter and the radio communication range is explored, and it is shown that by setting the -parameter appropriately, one can compute the network -shape locally.