DIMACS TR: 93-12
A Tight Bound for Edge Guards in Rectilinear Monotone Polygons
Author: Iliana Bjorling-Sachs
ABSTRACT
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