An O(lg lg OPT)-Approximation Algorithm for Multi-guarding Galleries

作者：Kirkpatrick David^*

来源：Discrete & Computational Geometry, 2015, 53(2): 327-343.

DOI：10.1007/s00454-014-9656-8

• Art gallery problem
• Polygon guarding
• Approximation algorithm
• Epsilon-net

We consider a generalization of the familiar art gallery problem in which individual points within the gallery need to be visible to some specified, but not necessarily uniform, number of guards. We provide an -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 -multinets of size for the instances of Multi-HittingSet associated with our multi-guarding problem. We then apply a now-standard linear-programming technique to build an approximation algorithm from this -multinet finder. This paper corrects, and simplifies the analysis of, the -time -net-finder described in [26], that was used to build an -approximation algorithm for the standard guarding problem in which all points within the gallery are required to be visible to at least one guard.

• 出版日期2015-3