An $O(\lg \lg \opt)$-Approximation Algorithm\\ for Multi-Guarding Galleries
Abstract: We consider a generalization of the familiar art gallery problem in
which individual points within the gallery need to be visible to some
specified, \emph{but not necessarily uniform}, number of guards. We provide an
$O(\lg \lg \opt)$-approximation algorithm for this multi-guarding problem in
simply-connected polygonal regions, with a minimum number of vertex guards
(possibly co-located). Our approximation algorithm is based on a
polynomial-time algorithm for building what we call $\eps$-multinets of size
$O(\frac{1}{\eps}\lg \lg \frac{1}{\eps})$ for the instances of the
multi-hittingset problem associated with our multi-guarding problem. We then
apply a now-standard linear-programming technique to build an approximation
algorithm from this $\eps$-multinet finder.
We also discuss the variant of multi-guarding in which co-location of guards is
not permitted.
[Based, in part, on joint work with D. Busto, W. Evans and J. King.]