Illuminating disjoint line segments in the plane (Q1434256)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Illuminating disjoint line segments in the plane |
scientific article |
Statements
Illuminating disjoint line segments in the plane (English)
0 references
7 July 2004
0 references
In the Euclidean plane \(E^2\), let \(S\) be a set of points (light sources), and \(D\) be a family of objects. We say that the set \(S\) ``illuminates'' a point set \(P\) if for any \(p\in P\) there is some \(s\in S\) such that \(]p,s[\cap D=\emptyset\), and the whole family \(D\) is illuminated by \(S\) if any boundary point of every member of \(D\) is illuminated by some \(s\in S\). (Note that the concept of illumination used here equals the concept of ``visibility'' introduced by F. A. Valentine.) Improving older results, the author shows that if \(D\) consists of \(n\) disjoint line segments (each of them clearly forming its own boundary), \(\lfloor{(n+1)\over 2}\rfloor\) light sources are enough. He also considers ``free space illumination'' (i.e., illumination of the complement of the union of all objects, with respect to \(E^2\)) and proves that \(\lfloor{4(n+1)\over 5}\rfloor\) light sources are sufficient (and sometimes also necessary) to illuminate the free space and both sides of \(n\geq 2\) disjoint line segments in \(E^2\).
0 references
illumination
0 references
visibility
0 references
matching technique
0 references
dual graph
0 references
simple graph
0 references
convex partition
0 references