Art Gallery Problem

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