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.]