Illuminating polygons with vertex π-floodlights

By the art gallery theorem, $\lfloor n/3\rfloor$ guards at corners, each seeing in every direction, can watch any polygon with $n$ corners. If each corner may instead hold one floodlight that lights only a half-plane, how many floodlights are needed? The answer is known only to lie between about $9n/14$ and $2n/3$.

Problem

Let $P$ be a simple polygon with $n$ vertices. A vertex $\pi$-floodlight at a vertex $v$ illuminates every point of $P$ that is visible from $v$ and lies in a closed half-plane $H$ whose boundary line passes through $v$. As in the source, floodlights are inward-facing: near $v$, the half-plane $H$ contains the polygon if $v$ is a convex vertex, and lies inside the polygon if $v$ is a reflex vertex. At most one floodlight may be placed at each vertex. Let $g(n)$ be the least number such that every simple polygon with $n$ vertices can be fully illuminated by $g(n)$ such floodlights.

Question. Determine $g(n)$; in particular, determine $\lim_{n\to\infty} g(n)/n$, which is known to lie between $9/14$ and $2/3$ if it exists.

Background

Urrutia introduced illumination by floodlights, that is, guards with a restricted angle of vision, and raised this question in his survey of art gallery problems [1]. For any aperture smaller than $\pi$ there are polygons that cannot be illuminated even with a floodlight at every vertex [2], so $\pi$ is the natural threshold. If the apex may be anywhere in the polygon rather than at a vertex, $\lfloor n/3\rfloor$ $\pi$-floodlights always suffice [4], the same number as for ordinary guards, so the restriction to vertices is what makes the problem hard.

What is known

• Lower bounds. Santos found polygons needing $\lfloor 3(n-1)/5\rfloor$ inward-facing floodlights. Urrutia (2002) raised the fraction to $5/8$ by gluing copies of a 9-vertex polygon that needs 5 lights, and Speckmann and Tóth (2005) to $9/14$: some polygons need $9n/14-O(1)$ [3], [4].
• Upper bound. Speckmann and Tóth showed with pointed pseudo-triangulations that $\lfloor (2n-k)/3\rfloor$ edge-aligned $\pi$-floodlights suffice, where $k$ is the number of convex vertices; since $k\ge 3$, at most $\lfloor 2n/3\rfloor-1$ are needed [3].
• Special shapes. For monotone mountains (polygons made of one straight edge and an $x$-monotone chain), $\lceil n/2\rceil-1$ floodlights is tight (O'Rourke, 1997).

What would count as progress

• A family of polygons needing more than $9n/14$ floodlights asymptotically, with a proof; for one specific polygon the claim can be supported by an exhaustive search over the finitely many combinatorially different placements.
• A placement algorithm that provably uses at most $(2/3-\delta)n$ floodlights for some $\delta>0$; its output on any polygon can be checked by computing the illuminated region exactly.
• Exact values of $g(n)$ for small $n$, found by computer.

References

1. J. Urrutia, Art gallery and illumination problems, in Handbook of Computational Geometry, Elsevier (2000), 973–1027. doi:10.1016/B978-044482537-7/50023-1
2. V. Estivill-Castro, J. O'Rourke, J. Urrutia and D. Xu, Illumination of polygons with vertex lights, Inform. Process. Lett. 56 (1995), 9–13. doi:10.1016/0020-0190(95)00129-Z
3. B. Speckmann and C. D. Tóth, Allocating vertex $\pi$-guards in simple polygons via pseudo-triangulations, Discrete Comput. Geom. 33 (2005), 345–364. doi:10.1007/s00454-004-1091-9
4. J. O'Rourke, Visibility, chapter 33 in Handbook of Discrete and Computational Geometry, 3rd ed., CRC Press (2017). Preprint

Source

Imported from The Open Problems Project, Problem 23, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.