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
    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
    0 references
    illumination
    0 references
    visibility
    0 references
    matching technique
    0 references
    dual graph
    0 references
    simple graph
    0 references
    convex partition
    0 references

    Identifiers