View source for Art gallery theorems

{{TEX|done}}
A collection of results similar to Chvátal's original theorem (cf. [[Chvátal theorem|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|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|Chvátal theorem]]), $\lfloor n/4\rfloor$ diagonal guards [[#References|[a6]]], and $\lfloor n/4\rfloor$ vertex guards for orthogonal polygons (polygons whose edges meet orthogonally) [[#References|[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$) [[#References|[a6]]]; for coverage of both interior and exterior, one needs $\lceil n/2\rceil$ vertex guards [[#References|[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 [[#References|[a1]]], [[#References|[a4]]], and $\lfloor n/4\rfloor$ point guards for orthogonal polygons (independent of $h$) [[#References|[a3]]]. Both hole problems remain open for vertex guards. See [[#References|[a7]]] for a survey updating [[#References|[a6]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I. Bjorling-Sachs,   D. Souvaine,   "An efficient algorithm for guard placement in polygons with holes"  ''Discrete Comput. Geom.'' , '''13'''  (1995)  pp. 77–109</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  Z. Füredi,   D. Kleitman,   "The prison yard problem"  ''Combinatorica'' , '''14'''  (1994)  pp. 287–300</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F. Hoffmann,   "On the rectilinear art gallery problem" , ''Proc. Internat. Colloq. on Automata, Languages, and Programming 90'' , ''Lecture Notes in Computer Science'' , '''443''' , Springer  (1990)  pp. 717–728</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  F. Hoffmann,   M. Kaufmann,   K. Kriegel,   "The art gallery theorem for polygons with holes" , ''Proc. 32nd Found. Comput. Sci.''  (1991)  pp. 39–48</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Kahn,   M. Klawe,   D. Kleitman,   "Traditional galleries require fewer watchmen"  ''SIAM J. Algebraic Discrete Methods'' , '''4'''  (1983)  pp. 194–206</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J. O'Rourke,   "Art gallery theorems and algorithms" , Oxford Univ. Press  (1987)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  T. Shermer,   "Recent results in art galleries"  ''Proc. IEEE'' , '''80''' :  9  (1992)  pp. 1384–1399</TD></TR></table>