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 a1,...,an at n sites p1,..., pn 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 ai = a for all 1£ i £ n (the uniform case) and q = a1+...+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