Combinatorics and complexity of guarding polygons with edge and point 2-transmitters (Q1699283)

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.