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 de punts guarda un polígon si, per tot punt del polígon hi ha algun pertanyent a tal que la línia entre i no surti del polígon.

Cobertura mitjançant quatre càmeres d'aquesta galeria.

Dues dimensions modifica

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 modifica

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   guardes i que de vegades són necessaris per guardar un polígon simple amb   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 modifica

  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.

Bibliografia modifica