Next: Problem 24: Polygonal Curve
Up: The Open Problems Project
Previous: Problem 22: MinimumLink Path
Problem 23: Vertex πFloodlights
 Statement
 How many πfloodlights
are always sufficient
to illuminate any polygon of n vertices,
with at most one floodlight placed at each vertex?
An αfloodlight is a light of aperture α.
(We consider here "inwardfacing" floodlights, whose
defining halfspace lies inside the polygon, locally in the
neighborhood of the vertex. Other models of the problem
allow general orientations of floodlights or
restricted orientations (e.g., "edgealigned").)
 Origin
 Jorge Urrutia, perhaps first published in [Urr00].
 Status/Conjectures
 Open. Now known that the fraction of
n that always suffices lies between 5/8 and 2/3.
 Partial and Related Results
 It was established in [ECOUX95] that
for any
α < π, there is a polygon that cannot be
illuminated with an αfloodlight at each vertex.
When
α = π, n  2 lights (trivially) suffice.
So it is of interest
(as noted in [Urr00])
to learn whether a fraction of
n lights suffice for πfloodlights.
A (very) special case is that
⌈n/2⌉  1
is a tight bound for "monotone mountains" [O'R97].
Tóth established [Tót01]
that (roughly)
(3/4)n suffice, in the case of general orientation
floodlights (not necessarily inwardfacing).
A lower bound of
Santos, that
⌊3(n  1)/5⌋ inwardfacing floodlights
are necessary (or
⌊2(n  2)/5⌋ generally oriented floodlights),
stood for several years, but
just recently (Jan. 2002) Urrutia constructed examples,
based on stitching together copies of Fig. 1, that show that
5(k + 1)/(8k + 9) (inwardfacing) floodlights are necessary for each k,
thus improving the lower bound factor from 0.6 to 0.625.
Also, Speckmann and Tóth [ST01b]
showed that
⌊n/2⌋ vertex πfloodlights suffice
for general orientations, while
⌊(2n  c)/3⌋ suffice
for inwardfacing, edgealigned orientations,
where c is the number of convex vertices.
In particular, this reduced the upperbound fraction below 1.
Figure 1:
A polygon of 9 vertices that needs 5 vertex πlights.

 Appearances
 [MO01]
 Categories
 art galleries; visibility
 Entry Revision History
 J. Mitchell, 24 Jan 2001; J. O'Rourke, 2 Aug. 2001; 29 Aug. 2001; 23 Jan. 2002; 30 Sep. 2007.
 ECOUX95

V. EstivillCastro, Joseph O'Rourke, J. Urrutia, and D. Xu.
Illumination of polygons with vertex floodlights.
Inform. Process. Lett., 56:913, 1995.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 O'R97

Joseph O'Rourke.
Vertex πlights for monotone mountains.
In Proc. 9th Canad. Conf. Comput. Geom., pages 15, 1997.
 ST01b

Bettina Speckmann and Csaba D. Tóth.
Vertex πguards in simple polygons.
Technical report, ETH Zürich, December 2001.
 Tót01

Csaba D. Tóth.
Illuminating polygons with vertex πfloodlights.
In V. N. Alexandrov et al., editors, Proc. Int. Conf. on Comput.
Sci., volume 2073 of Lecture Notes Comput. Sci., pages 772781.
SpringerVerlag, 2001.
 Urr00

Jorge Urrutia.
Art gallery and illumination problems.
In JörgRüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 9731027. NorthHolland, 2000.
Next: Problem 24: Polygonal Curve
Up: The Open Problems Project
Previous: Problem 22: MinimumLink Path
The Open Problems Project  December 04, 2015