Illumination of polygons by 45\(^{\circ}\)-floodlights (Q1874365)

The subject of this paper is a variant of the art gallery problem. Let \(P\) be a simple closed polygonal domain. An \(\alpha \)-floodlight is a pair \((p,C_{\alpha })\) of a point \(p\) and a cone \(C_{\alpha}\) of aperture \(\alpha \) at apex \(p\). A set \(F\) of \(\alpha \)-floodlights (with fixed \(\alpha \in (0^\circ,360^\circ]\)) is said to illuminate \(P\) if for each point \(x\in P\) there is a floodlight \((p,C_{\alpha })\in F\) such that the straight line segment \(px\) is contained in \(P\cap C_{\alpha }\). Let \(f(n,\alpha)\) be the minimal number of \(\alpha \)-floodlights that can illuminate any simple polygon with \(n\) vertices. In two previous papers [Comput. Geom. 17, 121-134 (2000; Zbl 0968.68166); Comput. Geom. 21, 185-192 (2002; Zbl 0998.68193)] the author has studied the value of \(f(n,\alpha)\) for \(\alpha \geq 90^\circ\). The main theorem of the paper under review determines \(f(n,\alpha)\) for \(\alpha \in ( 45^\circ,60^\circ)\). This number is \(n-1\) if \(n\) is odd, and \(n-2\) if \(n\) is even. This is proved by showing that every simple polygon with \(2(\ell +1)\) vertices can be partitioned into \(\ell \) quadrilaterals (using up to \(\ell -1\) Steiner points), and using the fact that any quadrilateral can be illuminated by at most two \(45^\circ\)-floodlights.