Difference between revisions of "Chvátal theorem"
From Encyclopedia of Mathematics
Ulf Rehmann (talk | contribs) m (moved Chvatal theorem to Chvátal theorem over redirect: accented title) |
(TeX) |
||
| 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 | + | 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 | + | 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=23236
Chvátal theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chv%C3%A1tal_theorem&oldid=23236
This article was adapted from an original article by J. O'Rourke (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article