Open Problems in the Combinatorics of Visibility and Illumination

Last update to this page:

I will post notices of solutions to the open problems listed in the paper. Please keep me apprised of progress!
  1. Illuminating Rectangles. I quoted a lower bound of n-1 and an upper bound of ~(4/3)n in the paper. Jorge Urrutia shows in his chapter, "Art gallery and illumination problems" (to appear in the North-Holland Handbook of Computational Geometry) that the Hoffman-Kaufman-Kriegel [n/4] result on orthogonal art galleries with holes establishes immediately that n+1 lights suffice. So the lower and upper bounds are nearly identical now: [n-1,n+1].

  2. Stage Illumination. Proven NP-complete, even with these restrictions: the floodlights are all affixed to just two points, and those points have the same x coordinate, or the same y coordinate. See:

    H. Ito, H. Uehara, M. Yokayama, "NP-completeness of stage illumination problem", Proc. Japan Conf. Discrete Comput. Geom. '98, Tokyo, 1998, pp. 88-92.

  3. Box Visibililty Graphs. Our results for bounds on the largest complete graph that is a visibility graph have been improved by Sandor Fekete and Henk Meijer: K_56 is a box visibility graph, but K_184 is not.

    See their 1996 Technical Report.

O'Rourke Homepage