# Art Gallery Problem

Jump to navigation
Jump to search

## Classic Problem

Consider an art gallery whose shape is a (simple) polygon.

The **Art Gallery Problem** asks:

- What is the minimum number of security guards needed, positioned on the perimeter of the art gallery, so that every point within the gallery can be seen by at least one of the guards?

That is, for a given (simple) polygon $P$:

- What is the smallest set $S$ of points on the perimeter of $P$ such that for every point $p \in P$ there exists some $q \in S$ such that there exists a straight line segment $p q$ lying wholly inside $P$?