On 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 furthest set of nodes as beacons. Network edges may also bound routing holes in the network, regions of failure due to environmental effects, or indicate the need for additional deployment. In this paper we explore the potential to solve the edge detection problem using a geometric structure called the alpha-shape (α-shape). 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 the disciplines of molecular biology, particle physics, and others. We explore the relationship between the α parameter and radio communication range and show that, by setting the α parameter appropriately, it is possible to compute the network α-shape locally.