DIMACS TR: 93-12

A Tight Bound for Edge Guards in Rectilinear Monotone Polygons

Author: Iliana Bjorling-Sachs


In this paper we examine a variation of the art gallery problem with each guard allowed to patrol along a designated wall of the gallery and with the gallery itself restricted to the shape of a rectilinear monotone polygon. We show that any such gallery with n vertices is completely covered by at most ceiling of (n-2)/6 guards and that this bound is tight. In addition we give an algorithm for placing the guards, which runs in O(n) time.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-12.ps
DIMACS Home Page