The 3-dimensional Searchlight Scheduling Problem
Giovanni Viglietta, Maurizio Monge · 2010
The problem of searching for a mobile intruder in a polygonal region by a set of stationary guards, each carrying an orientable laser, is known in the literature as the Searchlight Scheduling Problem. A long-standing conjecture concerns the NP-hardness of deciding if a given polygon is searchable by a given set of guards. In this paper we introduce the more general problem of detecting an intruder in a 3-dimensional polyhedral region by a set of searchplanes within a given time, and we prove its NP-hardness.