Hole detection or: ‘how much geometry hides in connectivity

Wireless sensor networks typically consist of small, very sim-ple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly, but have no idea about their rela-tive geographic locations. We examine how much geome-try information is nevertheless hidden in the communica-tion graph of the network: Assuming that the connectivity is determined by the well-known unit-disk graph model, we prove that using an extremely simple linear-time algorithm one can identify nodes on the boundaries of holes of the net-work. That is, there is enough geometry information hidden in the connectivity structure to identify topological features – in our example the holes in the network. While the theo-retical analysis turns out to be quite conservative, an actual implementation shows that the algorithm works well under less stringent conditions