Illumination of Orthogonal Polygons with Orthogonal Floodlights
James M. Abello, Vladimir Estivill‐Castro, Thomas Caton Shermer, Jorge Urrutia · International Journal of Computational Geometry & Applications · 1998
We provide the first tight bound for covering an orthogonal polygon with n vertices and h holes with vertex floodlights (guards with restricted angle of vision). In particular, we provide tight bounds for the number of orthogonal floodlights, placed at vertices or on the boundary, sufficient to illuminate the interior or the exterior of an orthogonal polygon with holes. Our results lead directly to very simple linear, and thus optimal, algorithms for computing a covering of an orthogonal polygon.