Illuminating labyrinths. (Q1428567): Difference between revisions

A labyrinth is defined as a set of line segments \(L\) with pairwise disjoint relative interiors and their complement \(E^{2}\diagdown \bigcup L\) connected. In the paper the variants of the illumination problem previously considered for disjoint line segments are presented and analogous lower and upper bounds for minimum number of light sources sufficient for any labyrinth of \(n\) line segments are deduced. The results obtained in the theorems are as follows: For the in-door illumination of the plane in the presence of a labyrinth of \(n\), \(n\geq 3\), line segments, \(n-1\) light sources are always sufficient and sometimes necessary. For the in-door illumination of the plane in the presence of an orthogonal labyrinth of \(n\), \(n\geq 4\) line segments, \(\left\lfloor 3(n+1)/4\right\rfloor \) light sources are always sufficient and sometimes necessary. For the in-door illumination of lines the following theorems are proved: For the in-door illumination of a labyrinth of \(n\) line segments \(\left\lfloor 3(n+1)/4\right\rfloor \) light sources are always sufficient and \(\left\lfloor 2(n-1)/3\right\rfloor \) are sometimes necessary. For the in-door illumination of \(n\), non-crossing line segments, \(\left\lfloor 9n/13\right\rfloor +1\) light sources are always sufficient and \(\left\lfloor 3(n-1)/5\right\rfloor \) are sometimes necessary.