An O(1)-approximation algorithm for the 2-dimensional geometric freeze-tag problem

The problem of awaking a swarm of asleep robots, starting with only one awake robot, is named the Freeze-Tag Problem (FTP). Waking up a robot is done by having an awake robot move to its position. Once a robot is awakened, it can assist in awaking others. In the FTP, the objective is to wake up all the robots in the shortest time possible. This problem is NP-Hard in general; the complexity of the geometric variant in the Euclidean plane is open. Arkin et al. [1] have given a constant-factor approximation algorithm, running in time O(nlog⁡n), for the geometric FTP, and utilized it as the basis of a PTAS. In this paper, we propose a simple O(n)-time constant-factor approximation algorithm, for the 2-dimensional geometric FTP.