NP-harte Probleme für minimale Polygonüberdeckungen. (NP-hard problems for minimal polygon coverings) (Q811138)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4215404
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | NP-harte Probleme für minimale Polygonüberdeckungen. (NP-hard problems for minimal polygon coverings) |
scientific article; zbMATH DE number 4215404 |
Statements
NP-harte Probleme für minimale Polygonüberdeckungen. (NP-hard problems for minimal polygon coverings) (English)
0 references
1988
0 references
A simple polygon P is visible from a set \(L\subseteq P\) if and only if for any point \(y\in P\) there exists a point \(x\in L\) such that xy\(\subseteq P\). If P is visible from L, then L is called a cover of P. On the basis of classification of covers, problems of computing the number of components of minimal covers (covers of a certain type consisting of a minimal number of components) are characterized to be NP- hard.
0 references
simple polygon
0 references
classification of covers
0 references
computing the number
0 references
components of minimal covers
0 references
0.8982729911804199
0 references
0.8966981172561646
0 references
0.8619380593299866
0 references
0.857990562915802
0 references
