Further NP-hard problems for minimal polygon coverings (Q1200939)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Further NP-hard problems for minimal polygon coverings |
scientific article |
Statements
Further NP-hard problems for minimal polygon coverings (English)
0 references
16 January 1993
0 references
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.
0 references
\(NP\)-problems
0 references
art gallery problems
0 references