Abstract: | What is the minimal number of light sources which is always sufficient to illuminate the plane in the presence of n disjoint opaque line segments? For n 5, O'Rourke proved that 2n/3 light sources are always sufficient and sometimes necessary, if light sources can be placed on the line segments and thus they can illuminate both sides of a segment.We prove that 2(n+1)/3 light sources are always sufficient and sometimes necessary, if light sources cannot be placed on the line segments. An O(nlogn) time algorithm is presented which allocates at most 2(n+1)/3 light sources collectively illuminating the plane. |