El problema de la galería de artes

Presentación sobre el NP-problem galería de artes.

1. EL PROBLEMA DE LA
GALERÍA DE ARTES
JUAN MANUEL MEJÍA BOTERO
SEBASTIAN LÓPEZ VALENCIA
Imagen tomada de:
http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Art_gallery_problem.svg/220px-
Art_gallery_problem.svg.png

2. Objetivos:
›Algo de historia…
›Definiciones necesarias para entender el problema.
›Más a fondo sobre el problema de la galería.
›Solución más popular.
›Posibilidades y derivados del planteamiento
original.

3. Autor del planteamiento:
›En 1973 el matemático norteamericano, Victor Klee
(en la foto) fue quien propuso el problema a su
colega el informático teórico checo-canadiense
Václav Chvátal el problema de la galería de arte.
Imagen tomada de:
http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Victo
r_Klee_MFO.jpg/200px-Victor_Klee_MFO.jpg

4. El problema…
›“¿Cuál es el mínimo número de guardas o cámaras
de vigilancia que necesitan para vigilar una galería
de arte?”
Imagen tomada de: https://mnmstatic.net/cache/20/21/thumb_medium-
2105710.jpg

5. Términos y definiciones necesarias:
›Galería: Polígono simple en el plano (bidimensional)
que tiene n lados y dichos lados, o paredes, no se
intersecan.
›Guardas: o cámaras: Los guardas tienen un punto
fijo. Lo mismo las cámaras. Las cámaras cubren
cualquier dirección (360°).Tanto guardias como
cámaras deben ser puestos dentro de la galería.

6. Términos y definiciones necesarias:
›Lugares vigilados: Aquellos puntos de la galería que
son visibles por una cámara o vigilante. Es decir,
son aquellos puntos de la galería que se pueden
conectar mediante un segmento con el punto
(guarda o cámara) que está vigilando.
Imagen tomada de:
http://blogs.20minutos.es/mati-una-
profesora-muy-
particular/files/2012/06/arte2.jpg

7. Dominio del problema:
›El problema pertenece en las matemáticas al área
de la geometría combinatoria; en informática
pertenece al área de la geometría computacional.
En la imagen se aprecia un ejemplo
De modelación
Imagen tomada de:
http://upload.wikimedia.org/wikipedia/commons/8/82/Cilindro_c
omp.jpg

8. Propuesta para
resolver el problema
de la galería

9. La solución:
›Václav Chvátal (en la foto) publicó su solución al
problema en 1975 en la revista: Journal of
Combinatory Theory.
›Sin embargo, la solución con demostración más
popular fue la del matemático Steve Fisk propuesta
en 1978 y afamada por su simpleza en la
demostración.
Imagen tomada de:
http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Chvata
l-kyoto2007-costume-head.png/160px-Chvatal-kyoto2007-
costume-head.png

10. Resultados obtenidos:
›Cota superior: “El número de cámaras mínimo que
se necesita para vigilar toda la galería de arte es
menor o igual al número de vértices del polígono.”
›Teorema: Para vigilar una galería de arte poligonal
de n vértices son suficientes n/3 cámaras (tomando
el mayor entero que es mejor o igual que n/3).

11. Resultados obtenidos:
›Si la galería está representada por un polígono
convexo, sólo se requiere una cámara. Esto
teniendo en cuenta que el rango visual del vigilante
y la cámara no tiene límite por distancia sino por
paredes y objetos.
Imagen tomada de:
http://culturacientifica.com/wp-
content/uploads/2014/01/IMAGEN-4.png

12. Enlaces
›http://blogs.20minutos.es/mati-una-profesora-muy-pa
rticular/tag/teorema-de-la-galeria-de-arte
/.
›http://culturacientifica.com/2014/01/29/teorema-de-l
a-galeria-de-arte
/.
›http://en.wikipedia.org/wiki/Art_gallery_problema.