next up previous
Next: Problem 24: Polygonal Curve Up: The Open Problems Project Previous: Problem 22: Minimum-Link Path

Problem 23: Vertex π-Floodlights

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 "inward-facing" 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., "edge-aligned").)
Jorge Urrutia, perhaps first published in [Urr00].
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 inward-facing). A lower bound of Santos, that ⌊3(n - 1)/5⌋ inward-facing 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) (inward-facing) 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 inward-facing, edge-aligned orientations, where c is the number of convex vertices. In particular, this reduced the upper-bound fraction below 1.
Figure 1: A polygon of 9 vertices that needs 5 vertex π-lights.
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.


V. Estivill-Castro, Joseph O'Rourke, J. Urrutia, and D. Xu.
Illumination of polygons with vertex floodlights.
Inform. Process. Lett., 56:9-13, 1995.

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

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

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

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 772-781. Springer-Verlag, 2001.

Jorge Urrutia.
Art gallery and illumination problems.
In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 973-1027. North-Holland, 2000.

next up previous
Next: Problem 24: Polygonal Curve Up: The Open Problems Project Previous: Problem 22: Minimum-Link Path
The Open Problems Project - September 19, 2017