Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots

We study the following connectivity formation problem: Robots equipped with radio transmitters with a bounded communication range are scattered over a large area. They would like to relocate so as to form a connected network as soon as possible. Where should each robot move? We present an $O(\sqrt{n})$-factor approximation algorithm for this problem when $n$ robots are initially distributed uniformly at random in a bounded area. In addition to analytical proofs, we verify the performance of our algorithm through simulations.