Problema del guarda del museu

El problema del guarda del museu és un problema de visibilitat molt estudiat en l'àmbit de la geometria computacional. Sorgeix d'un problema real en què cal vigilar una galeria d'art amb el mínim nombre de guardes, tal que tota la galeria quedi vigilada. També conegut com a problema de la galeria d'art o, simplement, problema del museu, la versió de geometria computacional la galeria es representa per un polígon i cada guarda per un punt en el polígon. Es diu que un conjunt $S$ de punts guarda un polígon si, per tot punt $p$ del polígon hi ha algun $q$ pertanyent a $S$ tal que la línia entre $p$ i $q$ no surti del polígon.

Dues dimensions

El 1973 Victor Klee va proposar per primera vegada el problema de la galeria d'art i des de llavors han sorgit nombroses variacions del problema inicial. En algunes versions, els guardes tenen un perímetre restringit o fins i tot han d'estar necessàriament als vèrtexs del polígon. En algunes versions només cal vigilar el perímetre o un subconjunt del perímetre.

Resolent la versió en la que els guardes s'han de col·locar ens els vèrtexs i en la que només s'han de vigilar els vèrtexs és equivalent a resoldre el problema del conjunt dominant en el graf de visibilitat del polígon.

El teorema de la galeria d'art de Chvátal

El teorema de la galeria d'art de Chvátal pren el nom de Václav Chvátal,^[1] dona una fita superior pel nombre mínim de guardes necessari. Afirma que sempre són suficients $\left\lfloor {\frac {n}{3}}\right\rfloor$ guardes i que de vegades són necessaris per guardar un polígon simple amb $n$ vèrtexs.

El 1973, en Victor Klee va proposar a Chvátal el problema de trobar quants vèrtexs/guardes calien. Chvátal ho va demostrar poc temps després. Posteriorment Steve Fisk va simplificar la demostració de Chvátal utilitzant un acoloriment amb 3 colors.

Referències

↑ Chvátal, V. «A combinatorial theorem in plane geometry». Journal of Combinatorial Theory, Series B, 18, 1975, p. 39–41. DOI: 10.1016/0095-8956(75)90061-1.

Bibliografia

O'Rourke, Joseph. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. ISBN 0-19-503965-3. Arxivat 2009-02-18 a Wayback Machine.
Shermer, Thomas «Recent Results in Art Galleries». Proceedings of the IEEE, 80, 1992, pàg. 1384–1399. DOI: 10.1109/5.163407.

[Chvatal-1] Chvátal, V. «A combinatorial theorem in plane geometry». Journal of Combinatorial Theory, Series B, 18, 1975, p. 39–41. DOI: 10.1016/0095-8956(75)90061-1.

[1]