Insights on Hidden Edge Guards and Guard Varieties

Explore various studies and findings on hidden edge guards with a focus on Victor Klee's Art Gallery Problem, the restriction of guards not seeing each other by Thomas Shermer, and different guard varieties. Discover the challenges and solutions associated with guarding polygons in different configurations.

• Edge Guards
• Hidden Guards
• Guard Varieties
• Polygon Guarding
• Security

meto391 Follow

Uploaded on Sep 23, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Some Results on Hidden Edge Guards Sarah Cannon Diane Souvaine Andrew Winslow

2. Klees Art Gallery Problem Consider the floor plan of an art gallery, and point guards that stand stationary and look in all directions. Victor Klee (1973): How many guards are needed to see the entire floor plan?

3. Hidden Guards In 1989, Thomas Shermer considered the same problem with the restriction that guards cannot see each other. BAD OK

4. Hidden Guards For hidden guards restricted to vertices, Shermer found that some polygons do not admit guarding! T. Shermer, Hiding people in polygons, Computing, 1989.

5. Are there other guard varieties for which some polygons do not admit guarding?

6. Edge Guards

7. Edge Definitions Historically, edge guards have included the endpoints. Recently, excluding the endpoints has been considered. CLOSED OPEN

8. Hidden Closed Edge Guards YES NO YES NO

9. Hidden Open Edge Guards YES NO NO YES

10. Results for Hidden Edge Guards Open Edges Closed Edges Not all simple polygons admit guarding. Not all monotone polygons admit guarding. Not all starshaped polygons admit guarding. All orthogonal polygons admit guards. Not all orthogonal polygons admit guarding. Guardable polygons may require n-22 edges. Guardable polygons may require (n-12)/3 guards.

11. Admissibility This polygon cannot be guarded by open or closed hidden edge guards.

12. Admissibility This polygon cannot be guarded by open or closed hidden edge guards.

13. Admissibility This polygon cannot be guarded by open or closed hidden edge guards.

14. Combinatorics Antiforcing gadget

15. Thank you