Connecting guards with minimum Steiner points inside simple polygons (Q2419109)

In the paper the authors study the problem of minimum connected Steiner guard set, which is a variant of the well-known art gallery problem. In this variant we have a simple polygon \(P\) and a finite set of points \(Q\) (the so-called terminal guards) inside \(P\). We are looking for a set \(S\) of minimum possible size such that the visibility graph of the points \(Q \cup S\) with respect to \(P\) is a connected graph. The points from the set \(S\) are called the Steiner guards. Depending on the restrictions for the locations of the terminal or Steiner guards (i.e., the vertices of \(P\), the boundary of \(P\), any point inside \(P\)) the authors consider nine versions of the problem. In each case the authors show that the problem is NP-hard and present \(O(1)\) factor approximation algorithms for minimizing the number of Steiner guards. In the algorithms they build a graph over a finite set of points of \(P\) on which an instance of the Steiner Tree Problem is solved. The weights of vertices and edges in these graphs are equal. Thus, minimizing the number of vertices is equal to minimizing the number of edges. Using an \(O(1)\) approximation factor algorithms for the Steiner Tree Problem for such graphs the authors prove that the approximation factors of the proposed algorithms are \(2.77\) for the version restricted to the boundary of \(P\) and \(1.39\) for the version restricted to the set of vertices of \(P\).