Problema del guarda del museu

De Viquipèdia
Dreceres ràpides: navegació, cerca

El problema de la galeria d'art o problema del museu és un problema de visibilitat que ha estat estudiat en profunditat en geometria computacional. Prové d'un problema de la vida real en què es tracta de vigilar una galeria d'art amb el mínim nombre de guardes tal que tots junts vigilin la totalitat de la galeria. En la versió de geometria computacional del problema 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.

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

Dues dimensions[modifica | modifica el codi]

El 1973 Victor Klee va proposar per primera vegada el problema de la galeria d'art.

Hi ha numeroses variacions dels problema inicial. En algunes versions els guardes tenen un perímetre restringit o fins i tot han d'estar necessariament 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 | modifica el codi]

El teorema de la galeria d'art de Chvátal pren el nom de Václav Chvátal,[1] dóna 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 a 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[modifica | modifica el codi]

  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 | modifica el codi]