The Open Problems Project

Next: Problem 24: Polygonal Curve Simplification

Previous: Problem 22: Minimum-Link Path in 2D

Problem 23: Vertex π\pi-Floodlights

Statement

How many π\pi-floodlights are always sufficient to illuminate any polygon of nn vertices, with at most one floodlight placed at each vertex? An α\alpha-floodlight is a light of aperture α\alpha. (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”).)

Origin

Jorge Urrutia, perhaps first published in [Urr00].

Status/Conjectures

Open. Now known that the fraction of nn that always suffices lies between 5/85/8 and 2/32/3.

Partial and Related Results

It was established in [ECOUX95] that for any α<π\alpha < \pi, there is a polygon that cannot be illuminated with an α\alpha-floodlight at each vertex. When α=π\alpha=\pi, n2n-2 lights (trivially) suffice. So it is of interest (as noted in [Urr00]) to learn whether a fraction of nn lights suffice for π\pi-floodlights. A (very) special case is that n/21\lceil n/2 \rceil-1 is a tight bound for “monotone mountains” [O'R97]. Tóth established [Tót01a] that (roughly) (3/4)n(3/4)n suffice, in the case of general orientation floodlights (not necessarily inward-facing). A lower bound of Santos, that 3(n1)/5\lfloor 3(n-1)/5\rfloor inward-facing floodlights are necessary (or 2(n2)/5\lfloor 2(n-2)/5\rfloor 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)5(k+1)/(8k+9) (inward-facing) floodlights are necessary for each kk, thus improving the lower bound factor from 0.60.6 to 0.6250.625. Also, Speckmann and Tóth [ST01b] showed that n/2\lfloor n/2\rfloor vertex π\pi-floodlights suffice for general orientations, while (2nc)/3\lfloor (2n-c)/3\rfloor suffice for inward-facing, edge-aligned orientations, where cc is the number of convex vertices. In particular, this reduced the upper-bound fraction below 11.

A polygon of 9 vertices that needs 5 vertex \pi-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.

Bibliography

[ECOUX95]

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

[MO01]

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.

[O'R97]

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

[ST01b]

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

[Tót01a]

Csaba D. Tóth. Illuminating polygons with vertex π\pi-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.

[Urr00]

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.