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!
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].
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.
H. Ito, H. Uehara, M. Yokayama,
"NP-completeness of stage illumination problem",
Proc. Japan Conf. Discrete Comput. Geom. '98,
Tokyo, 1998, pp. 88-92.
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.