The floodlight problem

Abstract

Given three angles summing to 2, given n points in the plane and a tripartition k1 + k2 + k3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains ki of the points. This new result on dissecting point sets is used to prove that lights of specied angles not exceeding can be placed at n xed points in the plane to illuminate the entire plane if and only if the angles sum to at least 2. We give O(n log n) algorithms for both these problems.