Art gallery theorems

A collection of results similar to Chvátal's original theorem (cf. Chvátal theorem). Each specifies tight bounds on the number of guards of various types that can visually cover a polygonal region. A guard $g\subset P$ sees a point $y$ if and only if there is an $x\in g$ such that the segment $xy$ is nowhere exterior to the closed polygon $P$. A polygon is covered by a set of guards if every point in the polygon is visible to some guard. Types of guards considered include point guards (any point $g\in P$), vertex guards ($g$ is a vertex of $P$), diagonal guards ($g$ is a nowhere exterior segment between vertices), and edge guards ($g$ is an edge of $P$). An art gallery theorem establishes the exact bound $G(n)$ for specific types of guards in a specific class of polygons, where $G(n)$ is the maximum over all polygons $P$ with $n$ vertices, of the minimum number of guards that suffice to cover $P$.

For simple polygons, the main bounds for $G(n)$ are: $\lfloor n/3\rfloor$ vertex guards (the Chvátal theorem), $\lfloor n/4\rfloor$ diagonal guards [a6], and $\lfloor n/4\rfloor$ vertex guards for orthogonal polygons (polygons whose edges meet orthogonally) [a5]. No tight bound for edge guards has been established.

Attention can be turned to visibility outside the polygon: for coverage of the exterior of the polygon, one needs $\lceil n/3\rceil$ point guards ($g$ any point not in the interior of $P$) [a6]; for coverage of both interior and exterior, one needs $\lceil n/2\rceil$ vertex guards [a2]. For polygons with $h$ holes and a total of $n$ vertices, the main results are: $\lfloor(n+h)/3\rfloor$ point guards for simple polygons [a1], [a4], and $\lfloor n/4\rfloor$ point guards for orthogonal polygons (independent of $h$) [a3]. Both hole problems remain open for vertex guards. See [a7] for a survey updating [a6].

References[edit]