Super Guarding and Dark Rays in Art Galleries
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908543961006080 |
|---|---|
| author | MIT CompGeom Group Akitaya, Hugo A. Demaine, Erik D. Hesterberg, Adam Lubiw, Anna Lynch, Jayson O'Rourke, Joseph Stock, Frederick |
| author_facet | MIT CompGeom Group Akitaya, Hugo A. Demaine, Erik D. Hesterberg, Adam Lubiw, Anna Lynch, Jayson O'Rourke, Joseph Stock, Frederick |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04613 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Super Guarding and Dark Rays in Art Galleries MIT CompGeom Group Akitaya, Hugo A. Demaine, Erik D. Hesterberg, Adam Lubiw, Anna Lynch, Jayson O'Rourke, Joseph Stock, Frederick Computational Geometry Metric Geometry 52C99 F.2.2; G.2.2 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. |
| title | Super Guarding and Dark Rays in Art Galleries |
| topic | Computational Geometry Metric Geometry 52C99 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2404.04613 |