Approximating Art Galleries

Suppose a 2D map of an art gallery is given by a polygon $P$, having $n$ corners (vertices) and $n$ walls (edges). If a watchman sees everything that lies on a straight line from his position, then the maximal number of guards needed is $\left\lfloor \frac{n}{3} \right\rfloor$ [12]. Finding the minimum number of watchmen needed for this task is NP hard, since it can be reduced to the 3-SAT problem [12]. Banos et al. reduce the art gallery problem to set cover and approximate the latter one. Set cover is defined as follows: Given a pair $(X,F)$, where $X$ is some finite set. $F$ is a subset of the power set of $X$, i.e., $(F \subset P(X))$ and $X = \bigcup_{s \in F} s$. Find the $C \subset F$, such that $X = \bigcup_{s \in C} s$ and the set $C$ has a minimum number of elements. The reduction of the art gallery to the set cover problem is randomized and can be stated as: 1. Generate randomly $n_K$ candidate positions in the interior of the polygon (map). 2. Calculate for all candidate positions the part of the polygon that is visible. 3. Approximate the set cover problem, i.e., find a minimal set of candidate positions from which the entire polygon is visible. A greedy algorithm approximates the set cover problem fast and with a good approximation ratio.