Super Guarding and Dark Rays in Art Galleries

Autor:	MIT CompGeom Group, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam, Lubiw, Anna, Lynch, Jayson, O'Rourke, Joseph, Stock, Frederick
Rok vydání:	2024
Předmět:	Computer Science - Computational Geometry Mathematics - Metric Geometry 52C99 F.2.2 G.2.2
Druh dokumentu:	Working Paper
Popis:	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. Comment: 23 pages, 16 figures, 9 references
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2404.04613 Zobrazit plný text záznamu View this record from Arxiv