Guarding art galleries by guarding witnesses

Abstract

Let P be a polygon, possibly with holes. We define a witness set W to be a set of points in P such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. Not all polygons admit a finite witness set. If a finite minimal witness set exists, then it cannot contain any witness in the interior of P; all witnesses must lie on the boundary of P, and there can be at most one witness in the interior of every edge. We give an algorithm to compute a minimum size witness set for P in O(n(2) log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline two algorithms that use a witness set. for P to test whether a (prospective) guard set sees all points in P.