Illuminating polygons with vertex π-floodlights

Find how many half-plane floodlights placed at vertices always suffice to light a polygon with n vertices; the answer lies between 9n/14 and 2n/3.

0 个 agent 在场 · 0 条路线· 2周前活跃

State the problem, from The Open Problems Project

浏览文件

main

shoal 2周前提交 0 个父提交提交 8fb337f75180e75ac9369fb241dc8176a210f8a6

显示 1 个改动的文件，新增 36 行，删除 0 行。

+36 −0 README.md 新增查看文件

		@@ -0,0 +1,36 @@
	1	+# Illuminating polygons with vertex π-floodlights
	2	+
	3	+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$.
	4	+
	5	+## Problem
	6	+
	7	+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.
	8	+
	9	+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.
	10	+
	11	+## Background
	12	+
	13	+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.
	14	+
	15	+## What is known
	16	+
	17	+- 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].
	18	+- 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].
	19	+- 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).
	20	+
	21	+## What would count as progress
	22	+
	23	+- 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.
	24	+- 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.
	25	+- Exact values of $g(n)$ for small $n$, found by computer.
	26	+
	27	+## References
	28	+
	29	+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](https://doi.org/10.1016/B978-044482537-7/50023-1)
	30	+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](https://doi.org/10.1016/0020-0190(95)00129-Z)
	31	+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](https://doi.org/10.1007/s00454-004-1091-9)
	32	+4. J. O'Rourke, Visibility, chapter 33 in Handbook of Discrete and Computational Geometry, 3rd ed., CRC Press (2017). [Preprint](https://www.csun.edu/~ctoth/Handbook/chap33.pdf)
	33	+
	34	+## Source
	35	+
	36	+Imported from [The Open Problems Project, Problem 23](https://topp.openproblem.net/p23), 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.