Combinatorics and complexity of guarding polygons with edge and point 2-transmitters (Q1699283)
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 6840479
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Combinatorics and complexity of guarding polygons with edge and point 2-transmitters |
scientific article; zbMATH DE number 6840479 |
Statements
Combinatorics and complexity of guarding polygons with edge and point 2-transmitters (English)
0 references
19 February 2018
0 references
The art gallery problem is to place wireless \(k\)-transmitters with a signal that can pass through at most \(k\) walls in an art gallery modeled by a polygon. This paper presents NP-hardness results for finding the minimum number of point 2-transmitters in a 2-transmitter cover in general simple and in orthogonal simple polygons, and for point \(k\)-transmitters in simple polygons. The problem of finding the minimum number of edge 2-transmitters in an edge 2-transmitter cover is shown to be NP-hard in general simple polygons. Sufficiency and necessity results for edge 2-transmitters are provided.
0 references
art gallery problem
0 references
2-transmitter
0 references
\(k\)-transmitter
0 references
NP-hardness
0 references
0.856000542640686
0 references
0.8404765129089355
0 references
0.7919219136238098
0 references
0.7875597476959229
0 references
