On guarding the vertices of rectilinear domains (Q2477198)

Two problems on visibility coverage are studied. One is the problem of guarding the vertices of a rectilinear polygon \(P\), which is considered in three different versions which are proved to be NP-hard. The three cases are the following: 1) guards may lie anywhere on the boundary of \(P\), 2) guards may lie only at vertices of \(P\), 3) guards may lie anywhere in \(P\). A 1.5D rectilinear terrain, which is defined by an \(x\)-monotone chain \(T\) of horizontal and vertical line segments, is the region to be guarded in the second problem considered in the article. A connection is established between this problem and the problem of computing a minimum clique cover in chordal graphs. A \(2\)-approximation algorithm for the guarding problem is described. Each part of the article is summarized in terms of a theorem.