Illumination in the presence of opaque line segments in the plane

摘要

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 lien segments. An O(n log n) time algorithm is presented which allocates at most [2(n + 1)/3] light sources collectively illuminating the plane.