Art gallery problem

[mklabgr]

Art gallery problem

Summary

The Art Gallery Problem is a classic problem in computational geometry that asks: What is the minimum number of guards needed to observe every point inside an art gallery? The gallery is modeled as a simple polygon, and a guard can see any point connected to it by a line segment that remains inside the polygon. A fundamental result, known as Chvátal’s Art Gallery Theorem, states that any simple polygon with n vertices can always be fully guarded by at most $⌊n/3⌋$ guards, and that this bound is sometimes necessary. 
The problem has inspired numerous variations, including restrictions on where guards may be placed and extensions to three-dimensional spaces, and it has applications in robotics, computer vision, wireless network coverage, surveillance, and stage lighting. Determining the minimum number of guards for a given polygon is computationally difficult and remains an important topic in geometry and algorithm design. 

ARTICLE