Traditional Galleries Require Fewer Watchmen

Abstract

Chvátal’s watchman theorem shows if the walls of an art gallery form an n-sided polygon then at most $[ n /3 ]$ watchmen are needed to guard it, and that this number is best possible. In this paper it is shown that if every pair of adjacent sides of the polygon form a right angle then at most $[ n / 4 ]$ guards are needed, and again this result is best possible. Our proof depends on showing that any finite region bounded by a finite number of edges, each of which lies parallel to one of a fixed pair of perpendicular axes, has a partition into convex quadrilaterals.