Modem illumination of monotone polygons (Q1699284)

The modem illumination problem is a generalization of the art gallery problem. In the latter, a polygonal art gallery has to place a minimum number of guards at well chosen positions in the polygon in such a way that they cover every point of the polygon. In the modem illumination problem, the guards are wireless modems that should be able to reach every point in the polygon given that they are strong enough to transmit a signal though \(k\)-walls. The art gallery problem corresponds to \(k=0\). Properties are proved such as: Every \((k+2)\)-gon \(P\) can be illuminated by a \(k\)-modem placed anywhere in \(P\). But better bounds for the number of \(k\)-modems needed are derived for \(n\)-gons under extra conditions. A polygon \(P\) is monotone if there is a direction \(d\) such that every line parallel to \(d\) divides \(P\) in at most 2 parts and it is called orthogonal if adjacent edges are orthogonal. It is proved that to illuminate a monotone \(n\)-gon at most \(\lceil \frac{n-2}{2k-3}\rceil\) \(k\)-modems are sufficient and sometimes necessary. If moreover \(P\) is orthogonal then \(m\) \(k\)-modems are sufficient and sometimes necessary where \(m=\lceil \frac{n-2}{2k+4}\rceil\) if \(k=1\) or even and \(m=\lceil \frac{n-2}{2k+6}\rceil\) for \(k\geq3\) and odd.