El problema de la galería de arte o problema del museo es un problema de visibilidad muy estudiado en la geometría computacional. La cuestión fue planteada por Victor Klee en 1973 en estos términos: Determinar el mínimo número de puntos de un polígono que son suficientes para ver a todos los restantes. Se puede interpretar también en términos de vigilancia de una sala poligonal. En la versión computacional del problema la galería de arte se representa con un polígono simple y cada guardia, cámara de seguridad o foco de luz se representa con un punto en el polígono.
Supongamos que usted tiene su propia galería de arte o museo con las pinturas más caras y cotizadas del mercado colgadas de las paredes de la misma y las esculturas más valoradas del mundo en su suelo. Usted estaría especialmente interesado en instalar un sistema de seguridad tal que estuviera compuesto por una colección de cámaras que se fijen en localizaciones establecidas pero que a su vez puedan rotar un giro de 360º, de forma que éstas puedan vigilar la galería en todas las direcciones. Se asume por simplicidad que nos movemos en un espacio dimensional, de forma que las cámaras se colocarán en un suelo plano de la galería.
A la colección de localizaciones en una galería estrellada donde se pueda colocar una única cámara de forma que se pueda observar la galería completa, se le denomina núcleo de la galería.
Asumiremos que contamos con una amplia y complicada galería de n paredes, cuyo valor n es bastante grande.
Imaginémonos ahora que el plano de una galería de arte viene representado por un polígono y es preciso iluminar su interior colocando guardias en sus vértices.
La cuestión trata de averiguar el número de guardias suficientes para iluminar completamente el polígono y dónde colocarlos. Evidentemente colocando un guardia en cada vértice del polígono el problema estaría resuelto, pero se trata de optimizar la iluminación. Para realizar esta optimización se puede enfocar de diferentes maneras.
La primera trataría de dado un polígono, encontrar el menor número de reflectores que se necesitan para iluminar su interior y la colocación de estos dentro del polígono. Este es un problema sumamente complicado, de hecho está catalogado entre los problemas computacionalmente intratables (NP-duro).
La segunda forma de enfocar el problema de optimización, consistiría en encontrar el número de reflectores que siempre son suficientes para vigilar todo el polígono de n lados.
Este problema se ha venido llamando problema de la galería de arte y fue propuesto por V. Klee en 1973. Dos años más tarde V. Chvátal lo resolvió. Enunciamos aquí el teorema :
Teorema de la Galería de Arte
n/3 guardias colocados en determinados vértices del polígono son siempre suficientes y ocasionalmente necesarios, para vigilar el interior de cualquier polígono simple de n lados.
vértices y más de 
aristas, entonces contiene un triángulo. El chiste es fijarse en en el vértice 
con mayor grado (del que salen más aristas), digamos que tiene grado 
. Si nos fijamos en los 
, entonces si 
no tiene un triángulo, ellos no pueden estar conectados entre sí, por lo que tienen grado a lo más 
. Los demás 
vértices tienen grado 
es el número de aristas de G. Después se usa media aritmética media geométria para probar que 
con lo que terminamos.
del otro. Esta gráfica es bipartita y sus vértices tienen grados mayores o iguales que los de G.
y vértices 
, 
, siempre hay una gráfica G’ bipartita con vértices 
tal que 
.
y vértices 
siempre hay una gráfica G’ 
-partita con vértices 
(ya tenemos la base con 
) de la misma manera que el caso base. Consideramos
por lo que podemos usar la base de inducción ahí y poner como otra componente a los vértices de 
.
– \in
– \notin
– \backsalsh
almita15
