Namespaces
Variants
Actions

Difference between revisions of "Art gallery theorems"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107201.png" /> sees a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107202.png" /> if and only if there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107203.png" /> such that the segment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107204.png" /> is nowhere exterior to the closed [[Polygon|polygon]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107205.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107206.png" />), vertex guards (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107207.png" /> is a vertex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107208.png" />), diagonal guards (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a1107209.png" /> is a nowhere exterior segment between vertices), and edge guards (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072010.png" /> is an edge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072011.png" />). An art gallery theorem establishes the exact bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072012.png" /> for specific types of guards in a specific class of polygons, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072013.png" /> is the maximum over all polygons <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072014.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072015.png" /> vertices, of the minimum number of guards that suffice to cover <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072016.png" />.
+
{{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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072017.png" /> are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072018.png" /> vertex guards (the [[Chvátal theorem|Chvátal theorem]]), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072019.png" /> diagonal guards [[#References|[a6]]], and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072020.png" /> vertex guards for orthogonal polygons (polygons whose edges meet orthogonally) [[#References|[a5]]]. No tight bound for edge guards has been established.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072021.png" /> point guards (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072022.png" /> any point not in the interior of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072023.png" />) [[#References|[a6]]]; for coverage of both interior and exterior, one needs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072024.png" /> vertex guards [[#References|[a2]]]. For polygons with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072025.png" /> holes and a total of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072026.png" /> vertices, the main results are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072027.png" /> point guards for simple polygons [[#References|[a1]]], [[#References|[a4]]], and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072028.png" /> point guards for orthogonal polygons (independent of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110720/a11072029.png" />) [[#References|[a3]]]. Both hole problems remain open for vertex guards. See [[#References|[a7]]] for a survey updating [[#References|[a6]]].
+
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====
 
====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>
 
<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>

Latest revision as of 12:32, 27 August 2014

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

[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
How to Cite This Entry:
Art gallery theorems. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Art_gallery_theorems&oldid=33153
This article was adapted from an original article by J. O'Rourke (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article