Paper by Erik D. Demaine
- MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Anna Lubiw, Jayson Lynch, Joseph O’Rourke, and Frederick Stock, “Super Guarding and Dark Rays in Art Galleries”, in Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023), July 31–August 4, 2023, pages 51–61.
We explore an Art Gallery variant where each point of a polygon must be seen
by k guards, and guards cannot see through other guards. Surprisingly,
even covering convex polygons under this variant is not straightforward. For
example, covering every point in a triangle k = 4 times (a
4-cover) requires 5 guards, and achieving a 10-cover requires 12
guards. Our main result is tight bounds on k-covering a convex polygon
of n vertices, for all k and n. The proofs of both upper
and lower bounds are nontrivial. We also obtain bounds for simple polygons,
leaving tight bounds an open problem.
- The paper is 11 pages.
- The paper is available in PDF (3424k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by