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.
- A seperation property of plane convex sets.
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Guarding rectangular art galleries
- scientific article; zbMATH DE number 4065813 (Why is no real title available?)
- scientific article; zbMATH DE number 177851 (Why is no real title available?)
- scientific article; zbMATH DE number 1241843 (Why is no real title available?)
- scientific article; zbMATH DE number 1424310 (Why is no real title available?)
- Illuminating rectangles and triangles on the plane
- Illumination in the presence of opaque line segments in the plane
- Illumination of convex discs
- Lower bounds on the cardinality of the maximum matchings of planar graphs
- Planar Ramsey numbers
This page was built for publication: Illuminating labyrinths.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1428567)
