The art gallery problem, also called the museum problem, is a well studied problem in computational geometry about visibility inside a room. It asks, in an art gallery represented as a simple polygon, what is the smallest number of guards, represented as points inside the polygon, needed so that every point in the gallery is visible to at least one guard, meaning the straight line segment between them stays entirely inside the polygon. The problem is studied for its own mathematical interest and also has applications outside pure geometry, including robotics, where an artificial intelligence must plan movement based on what it can see of its surroundings, as well as image editing, stage lighting design, and the placement of infrastructure such as natural disaster warning systems.
Facts
StatementTo guard a simple polygon with n vertices, floor(n/3) guards are always sufficient and sometimes necessary. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Art gallery problem (Wikipedia)
Sources
1. Art gallery problem (Wikipedia)
The theorem
To guard a simple polygon with n vertices, ⌊ n / 3 ⌋ guards are always sufficient and sometimes necessary.
History
Chvátal proved it shortly thereafter
In Branch: Geometry, Lead sentence
well-studied visibility problem in computational geometry.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.