Further NP-hard problems for minimal polygon coverings (Q1200939)

A set \(L\) of pairs \((k_ i,k_{i+1})\) of adjacent edges of a simple polygon \(P\) is called a cover of \(P\) if for each \(x\in P\) there exists a \(y\in k_ i\cup k_{i+1}\) (for a suitable (\(k_ i,k_{i+1})\in L\)) with \(xy\subseteq P\). The authors show that the problem of determining the minimal number \(m(L)\) of such ``guards'' for a given \(P\) with \(n\) vertices is \(NP\)-hard.