Imagine a thief is loose in a dark polygon. The polygon contains a number of “searchlights,” points that can shine a beam of light in any one direction. The novel problem introduced in this paper is to design a schedule for the rotation of the searchlights that will guarantee illumination of the thief, regardless of the thief’s cleverness and speed.
A single searchlight in the interior of a polygon is insufficient, as the thief could outrun any rotation of the beam. But if the searchlights are on the boundary and in the kernel of a star-shaped polygon, a single sweep will catch any thief.
The main achievement of this paper, aside from introducing the problem and making it precise, is a complete characterization of those polygons searchable by two searchlights. Let P be a polygon and x and y two searchlights in P. If at least one of the searchlights is on the boundary of P, the problem is relatively easy to solve. So suppose both x and y are interior to P. Certainly P must be the union of the points visible to x and those visible to y. Also, x and y must be visible to each other. These are obvious necessary conditions. Sufficient conditions are more subtle.
Let the chord L of the polygon containing xy be horizontal, with x to the left of y. L partitions the polygon boundary into above and below chains A and B. If xy does not meet the boundary of P, then P has a search schedule if and only if points a in A and b in B exist such that x can see the chain counterclockwise from b to a, and y can see the chain counterclockwise from a to b. When xy does meet the boundary, other similar but more specialized conditions obtain.
The proofs are delicate and difficult. The authors establish several tools for exploring beyond two searchlights, but the problem of characterizing polygons searchable by three searchlights remains “a challenging open problem.”