An Optimal Illumination Region Algorithm for Convex Polygons

For the convex polygon P having n vertices entirely contained in a convex polygon K having m vertices, an optimal algorithm with running time O(n + m) is presented to compute and name regions in the boundary of K from which it is possible to illuminate the exterior of P. It is also shown that this illumination region algorithm can be used to improve the worst case O(nm) running time of a related two dimensional simplex coverability algorithm so that it too has running time O(n + m), and is thus optimal to within a constant factor.