Portal de Periódicos da CAPES

Traditional Galleries Require Fewer Watchmen

1983; Society for Industrial and Applied Mathematics; Volume: 4; Issue: 2 Linguagem: Inglês

10.1137/0604020

2168-345X

Jonas Kahn, Maria Klawe, Daniel J. Kleitman,

Digital Image Processing Techniques

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.