Complexity of Floodlight Problems

There are several variants of this problem; we start with one that is to our knowledge still open. Consider the following decision problem FLOODLIGHT. You are given

The idea is that at each of the n points, there is a floodlight that diverges at the angle alpha. You may orient each light to point in any direction you like. The question is, can the lights be oriented such that I is completely illuminated? Note that we neglect shadows that one might envision appearing when one floodlight shines on another.

FLOODLIGHT is clearly in NP; given n angles, indicating an orientation for each of the n floodlights, whether or not I is completely illuminated using these orientations can be checking in polynomial time using a bit of trigonometry. We are concerned with the question of whether FLOODLIGHT is NP-complete or in P (or neither?).

Status

The problem as posed above is still open, but we have a few results relating to variants of the problem.

We have found that the original problem, as posed by Urrutia in 1992, has n angles in the input, so each of the n floodlights is given a different angle. This problem was shown to be NP-complete in 1998:

"NP-Completeness of Stage Illumination Problems"
Hiro Ito, Hideyuki Uehara, and Mitsuo Yokoyama.
Get the postscript from the citeseer entry
In this paper, NP-completeness of FLOODLIGHT is conjectured. Adapting their reduction (which uses PARTITION) to FLOODLIGHT appears difficult, but we have not ruled this out yet.

We have also determined that for any fixed alpha, there exists a constant k(alpha) such that given any k(alpha) points, floodlights with angle alpha can be oriented at the points to illuminate the entire x-axis. This result is written up here. A corollary is that the variation of the floodlight problem in which alpha is fixed can be solve in constant time. In that report, k(alpha) = ceiling(cot(alpha/2)) + 2*ceiling(pi/(4*alpha)). Will Evans has subsequently reduced it to ceiling(pi/alpha), and this bound is tight, since placing ceiling(pi/alpha)-1 floodlights all at one point cannot illuminate the entire x-axis.

We have also been toying with the idea of generalizing the problem to 3 dimensions. Here the floodlights would live in 3-space, all with positive y coordinates, and the goal is to illuminate some part of the y=0 plane. When alpha is fixed, we think we can define a constant k3(alpha) number of floodlights such that the entire y=0 plane can always be illuminated. However, it is unclear if such a result can be parlayed into a constant time algorithm, since we have no "brute-force" algorithm to invoke when confronted with less than k3(alpha) floodlights.