A generalized fortress problem using k-consecutive vertex guards

The fortress problemwas posed independently by Joseph Malkelvitch and Derick Wood to determine the number of guards sufficient to cover the exterior of an n-vertex polygon. O'Rourke and Wood showed that vertex guards are sometimes necessary and always sufficient. Yiu and Choi considered a variation of the problem by allowing each guard to patrol an edge (called an edge guard) of the polygon and obtained a tight bound of edge guards for general polygons. In this paper, we unify and generalize both results by considering the number of k-consecutive vertex guards that are required to solve the fortress problem. A tight bound of is obtained. Received 21 July 1999; revised 23 March 2000.