Hole Detection or: "How much Geometry hides in Connectivity?"
Stefan Funke, Christian Klein
Wireless sensor networks typically consist of small, very simple 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 relative geographic locations.
We examine how much geometry information is nevertheless hidden in the communication 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 network. 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 theoretical analysis turns out to be quite conservative, an actual implementation shows that the algorithm works well under less stringent conditions.
PDF