Date Added: Oct 2011
A key architectural goal in wireless adhoc networks is to ensure that each node in the network can communicate with every other node (perhaps by routing through other nodes). This requires that the nodes be connected through a communication overlay. The problem can be abstracted as such: given n points on the plane (each representing a wireless node), how efficiently can one ensure connectivity among the points? The notion of efficiency in a wireless setting is crucially dependent on that distinguishing feature of wireless networks: interference. Two or more simultaneous communications in the same wireless channel interfere with each other, potentially destroying all or some of the communications.