Galleries, light matchings and visibility graphs (Q4028896)

[For the entire collection see Zbl 0753.00021.] The following problem is considered: For a collection of \(n\) disjoint line segments on the plane a light placed at point \(x\) is said to illuminate a point \(y\) on the plane if the line \(xy\) does not cross the interior of any other line segment. How many such lights are needed to illuminate all of the points on all of the line segments? It is proved (using 4CT) that for any collection of \(n\) disjoint line segments on the plane, such that no two are parallel and no three extensions meet in a common point, \(\lceil 3n/4\rceil\) lights, none on any of the line segments, are occasionally necessary, and always sufficient for this. A polynomial time algorithm (with complexity \(O(n\log n))\) to assign these lights is proposed. Some variations of these problems are also considered (e.g. the problem of two-sided light illumination).