Illuminating polygons with vertex π-floodlights
Let $P$ be a simple polygon with $n$ vertices. A vertex $\pi$-floodlight at a vertex $v$ is a light of aperture $\pi$: it illuminates the points of $P$ visible from $v$ that lie in a half-plane $H$ bounded by a line through $v$. It is inward-facing if, near $v$, the half-plane $H$ lies inside $P$. (Other versions allow arbitrary orientations, or only edge-aligned ones.)
Estivill-Castro, O'Rourke, Urrutia and Xu showed that for every aperture $\alpha < \pi$ some polygon is not illuminated even by an $\alpha$-floodlight at each vertex, whereas $n-2$ vertex $\pi$-floodlights trivially suffice. Santos showed that $\lfloor 3(n-1)/5\rfloor$ inward-facing floodlights can be necessary, and Urrutia raised the necessary fraction of $n$ to $5(k+1)/(8k+9)$ for every $k$. Speckmann and Tóth showed that $\lfloor (2n-c)/3\rfloor$ inward-facing edge-aligned floodlights suffice, where $c$ is the number of convex vertices, and $\lfloor n/2\rfloor$ suffice with general orientations; for inward-facing lights the fraction of $n$ needed thus lies between $5/8$ and $2/3$.
Problem. How many inward-facing vertex $\pi$-floodlights, with at most one placed at each vertex, always suffice to illuminate a polygon with $n$ vertices?
Source: Urrutia, perhaps first published in Urrutia (2000); Problem 23 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- art gallery problem, floodlight illumination, The Open Problems Project
References
@incollection{urrutia2000,
author = {Urrutia, Jorge},
title = {Art gallery and illumination problems},
editor = {Sack, J{\"o}rg-R{\"u}diger and Urrutia, Jorge},
booktitle = {Handbook of Computational Geometry},
publisher = {North-Holland},
year = {2000},
pages = {973--1027},
}
@article{estivillcastroorourkeurrutiaxu1995,
author = {Estivill-Castro, V. and O'Rourke, Joseph and Urrutia, J. and Xu, D.},
title = {Illumination of polygons with vertex floodlights},
journal = {Inform. Process. Lett.},
volume = {56},
year = {1995},
pages = {9--13},
}
@inproceedings{orourke1997,
author = {O'Rourke, Joseph},
title = {Vertex $\pi$-lights for monotone mountains},
booktitle = {Proc. 9th Canad. Conf. Comput. Geom.},
year = {1997},
pages = {1--5},
}
@inproceedings{toth2001floodlights,
author = {T{\'o}th, Csaba D.},
title = {Illuminating polygons with vertex $\pi$-floodlights},
editor = {Alexandrov, V. N. and others},
booktitle = {Proc. Int. Conf. on Comput. Sci.},
series = {Lecture Notes Comput. Sci.},
volume = {2073},
publisher = {Springer-Verlag},
year = {2001},
pages = {772--781},
}
@techreport{speckmanntoth2001,
author = {Speckmann, Bettina and T{\'o}th, Csaba D.},
title = {Vertex {$\pi$}-guards in simple polygons},
institution = {ETH Z{\"u}rich},
year = {2001},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01077, "Illuminating polygons with vertex π-floodlights", clopen.solutions.