1997-12-01
The floodlight problem
Publication
Publication
International Journal of Computational Geometry and Applications , Volume 7 - Issue 1-2 p. 153- 163
Given three angles summing to 2π, given n points in the plane and a tripartition κ1 + k2 + κ3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains κi of the points. This new result on dissecting point sets is used to prove that lights of specified angles not exceeding π can be placed at n fixed 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.
Additional Metadata | |
---|---|
Dissecting point sets, Illumination problems | |
International Journal of Computational Geometry and Applications | |
Organisation | School of Computer Science |
Bose, P, Guibas, L. (Leonidas), Lubiw, A. (Anna), Overmars, M. (Mark), Souvaine, D. (Diane), & Urrutia, J. (Jorge). (1997). The floodlight problem. International Journal of Computational Geometry and Applications, 7(1-2), 153–163.
|