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$?