Convex and discrete geometry Discrete and combinatorial geometry Theorem

Art gallery theorem

Builds on Polygon triangulation Chromatic number

Statement

Let $P \subset \R^2$ be a simple polygon with $n \ge 3$ vertices. Say that a point $g \in P$ sees a point $x \in P$ when the segment from $g$ to $x$ lies in $P$ .

There is a set of at most $\floor{n/3}$ vertices of $P$ such that every point of $P$ is seen by at least one of them.
For every $n \ge 3$ there is a simple polygon $P$ with $n$ vertices that no set of fewer than $\floor{n/3}$ points of $P$ sees entirely.

Remarks

The theorem is due to Václav Chvátal; the short proof below is due to Steve Fisk. Take a triangulation of $P$ , and consider the graph whose edges are the sides of $P$ and the diagonals used. This graph can be properly coloured with $3$ colours (its chromatic number is $3$ ), by removing an ear triangle, colouring the rest, and giving the last vertex the missing colour. Each triangle then has one vertex of each colour. The smallest colour class has at most $\floor{n/3}$ vertices, and it contains a vertex of every triangle, which sees the whole triangle because triangles are convex.

For sharpness, a comb with $k$ narrow teeth has $n = 3k$ vertices, and no point sees into two different teeth, so $k = n/3$ guards are needed.

Going deeper

For a student

The proof is a model use of polygon triangulation: cut, colour, and count. The bound $\floor{n/3}$ is a worst case over all polygons; for a given polygon the minimum number of guards can be much smaller, and computing it is NP-hard. Many variants exist, such as orthogonal polygons, where $\floor{n/4}$ guards suffice, and polygons with holes.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`G4WSPQJ6W1`
URI	`m2://G4WSPQJ6W1`
Kind	statement, theorem
Writing	W0 stub
MSC	52C45, 68U05
Status	This copy of the site has no build data. Run `m2 status G4WSPQJ6W1`.
About	Polygon triangulation
Uses	Polygon triangulation, Chromatic number