Namespaces
Variants
Actions

Difference between revisions of "Chvátal theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 
''Chvátal watchman theorem''
 
''Chvátal watchman theorem''
  
The following question was posed by V. Klee: How many guards are necessary (and sufficient) to guard (visually cover) a polygonal room (an art gallery) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110230/c1102301.png" /> vertices?
+
The following question was posed by V. Klee: How many guards are necessary (and sufficient) to guard (visually cover) a polygonal room (an art gallery) of $n$ vertices?
  
The question was answered by V. Chvátal [[#References|[a1]]]. He proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110230/c1102302.png" /> guards are sometimes necessary and always sufficient to guard a polygonal room of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110230/c1102303.png" /> vertices.
+
The question was answered by V. Chvátal [[#References|[a1]]]. He proved that $\lfloor n/3\rfloor$ guards are sometimes necessary and always sufficient to guard a polygonal room of $n$ vertices.
  
 
A concise proof was later found by S. Fisk [[#References|[a2]]]. See also [[Art gallery theorems|Art gallery theorems]].
 
A concise proof was later found by S. Fisk [[#References|[a2]]]. See also [[Art gallery theorems|Art gallery theorems]].

Latest revision as of 12:23, 27 August 2014

Chvátal watchman theorem

The following question was posed by V. Klee: How many guards are necessary (and sufficient) to guard (visually cover) a polygonal room (an art gallery) of $n$ vertices?

The question was answered by V. Chvátal [a1]. He proved that $\lfloor n/3\rfloor$ guards are sometimes necessary and always sufficient to guard a polygonal room of $n$ vertices.

A concise proof was later found by S. Fisk [a2]. See also Art gallery theorems.

References

[a1] V. Chvátal, "A combinatorial theorem in plane geometry" J. Combin. Th. B , 18 (1975) pp. 39–41
[a2] S. Fisk, "A short proof of Chvátal's watchman theorem" J. Combin. Th. B , 24 (1978) pp. 374
How to Cite This Entry:
Chvátal theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chv%C3%A1tal_theorem&oldid=15611
This article was adapted from an original article by J. O'Rourke (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article