Visibility properties of polygons

David Bruce Glasser, University of Nevada, Las Vegas


Two problems dealing with visibility in the interior of a polygon are investigated. We present a linear time algorithm for computing the stair-case visibility polygon from a point inside a simple polygon, which is optimal within a constant factor. We show that the problem of locating the minimum number of 90{dollar}\sp\circ{dollar}-flood-lights to illuminate the interior of a simple polygon is NP-complete. We also discuss the generalization of the above results.