Next: Problem 24: Polygonal Curve Simplification
Previous: Problem 22: Minimum-Link Path in 2D
How many -floodlights are always sufficient to illuminate any polygon of 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 that always suffices lies between and .
It was established in [ECOUX95] that for any , there is a polygon that cannot be illuminated with an -floodlight at each vertex. When , lights (trivially) suffice. So it is of interest (as noted in [Urr00]) to learn whether a fraction of lights suffice for -floodlights. A (very) special case is that is a tight bound for “monotone mountains” [O'R97]. Tóth established [Tót01a] that (roughly) suffice, in the case of general orientation floodlights (not necessarily inward-facing). A lower bound of Santos, that inward-facing floodlights are necessary (or 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 (inward-facing) floodlights are necessary for each , thus improving the lower bound factor from to . Also, Speckmann and Tóth [ST01b] showed that vertex -floodlights suffice for general orientations, while suffice for inward-facing, edge-aligned orientations, where is the number of convex vertices. In particular, this reduced the upper-bound fraction below .
art galleries; visibility
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.