Matthew Cary,
Ashish Sabharwal ,
Atri Rudra and Erik Vee

**Floodlight Illumination of Infinite Wedges**

**Abstract :**
The floodlight illumination problem asks whether there exists a
one-to-one placement of *n* floodlights illuminating infinite wedges
of angles a_{1},...,a_{n} at *n* sites *p*_{1},...,
*p*_{n} in a plane such that a given infinite wedge
*W* of angle q
located at point *q* is completely illuminated by the floodlights. We
prove that this problem is NP-hard, closing an open problem from 2001.
In fact, we show that the problem is NP-complete
even when a_{i} =
a for all *1*£
*i* £ *n* (the
*uniform* case) and q =
a_{1}+...+a
_{n} (the *tight*
case). On the positive side, we describe sufficient conditions on the
sites of floodlights for which there are efficient algorithms
to find an illumination. We discuss various approximate solutions and
show that computing any *finite* approximation is NP-hard while
e-*angle* approximations can be obtained efficiently.

** Versions**
- Abstract in the 14th Annual Fall Workshop on Computational Geometry. November 2004.
- Full version submitted to Computation Geometry: Theory and Applications (CGTA). [PDF]