  Arkin et al. in 2002 introduced a scheduling-like problem called Freeze-Tag
Problem (FTP) motivated by robot swarm activation. The input consists of the
locations of n mobile punctual robots in some metric space or graph. Only one
begins "active", while the others are initially "frozen". All active robots can
move at unit speed and, upon reaching a frozen one's location, activates it.
The goal is to activate all the robots in the minimum amount of time, the
so-called makespan. Until 2017 the hardness of this problem in metric spaces
was still open, but then Yu et al. proved it to be NP-Hard in the Euclidian
plane, and in the same year, Demaine and Roudoy demonstrated that the FTP is
also hard in 3D with any $L_p$ distance (with p > 1). However, we still don't
know whether Demaine's and Roudoy's result could be translated to the plane.
This paper fills the p=1 gap by showing that the FTP is NP-Hard in 3D with
$L_1$ distance.
