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 sees a point
if and only if there is an
such that the segment
is nowhere exterior to the closed polygon
. 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
), vertex guards (
is a vertex of
), diagonal guards (
is a nowhere exterior segment between vertices), and edge guards (
is an edge of
). An art gallery theorem establishes the exact bound
for specific types of guards in a specific class of polygons, where
is the maximum over all polygons
with
vertices, of the minimum number of guards that suffice to cover
.
For simple polygons, the main bounds for are:
vertex guards (the Chvátal theorem),
diagonal guards [a6], and
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 point guards (
any point not in the interior of
) [a6]; for coverage of both interior and exterior, one needs
vertex guards [a2]. For polygons with
holes and a total of
vertices, the main results are:
point guards for simple polygons [a1], [a4], and
point guards for orthogonal polygons (independent of
) [a3]. Both hole problems remain open for vertex guards. See [a7] for a survey updating [a6].
References
[a1] | I. Bjorling-Sachs, D. Souvaine, "An efficient algorithm for guard placement in polygons with holes" Discrete Comput. Geom. , 13 (1995) pp. 77–109 |
[a2] | Z. Füredi, D. Kleitman, "The prison yard problem" Combinatorica , 14 (1994) pp. 287–300 |
[a3] | 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 |
[a4] | F. Hoffmann, M. Kaufmann, K. Kriegel, "The art gallery theorem for polygons with holes" , Proc. 32nd Found. Comput. Sci. (1991) pp. 39–48 |
[a5] | J. Kahn, M. Klawe, D. Kleitman, "Traditional galleries require fewer watchmen" SIAM J. Algebraic Discrete Methods , 4 (1983) pp. 194–206 |
[a6] | J. O'Rourke, "Art gallery theorems and algorithms" , Oxford Univ. Press (1987) |
[a7] | T. Shermer, "Recent results in art galleries" Proc. IEEE , 80 : 9 (1992) pp. 1384–1399 |
Art gallery theorems. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Art_gallery_theorems&oldid=16640