Modem Illumination of Monotone Polygons

Abstract

We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$-modems and study the minimum number of $k$-modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $\lceil \frac{n-2}{2k+3}\rceil$ $k$-modems. In addition, we exhibit examples of monotone polygons requiring at least $\lceil \frac{n-2}{2k+3}\rceil$ $k$-modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$, every such polygon can be illuminated with $\lceil \frac{n-2}{2k+4}\rceil$ $k$-modems, while for odd $k\ge 3$, $\lceil \frac{n-2}{2k+6}\rceil$ $k$-modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight.

full version, 21 pages, 14 figures