Universidad Politécnica de Madrid

Facultad de Informática

 

Trabajo Fin de Carrera

Iluminación de polígonos con reflectores

Autor: Bassam Al-Zarif Zabala

Tutor: Gregorio Hernández

 

Polígono Simple

Un polígono P se dice que es simple (o Jordan) si  los únicos puntos del plano que pertenecen a dos lados del polígono P son los vértices del polígono P. Cada polígono tiene definido un interior y un exterior. Los polígonos simples son topológicamente equivalentes a un disco.

Polígonos Ortogonales

Los polígonos ortogonales tienen un especial interés en el estudio de problemas de guardias. Un polígono ortogonal es aquel que tiene todos sus lados paralelos al eje x o al eje y. Además una de las principales motivaciones del estudio de estos polígonos es que en la “vida real” la mayoría de los edificios son “ortogonales”.

Polígono Monótono

La intersección del polígono con cualquier recta perpendicular a R, es o bien vacía o bien un punto o bien un segmento.

Un polígono P se dice que es monótono respecto de una dirección D si toda recta r ortogonal a la recta D verifica que

r ∩ P =

 

Se dice que P es monótono, si lo es respecto de alguna dirección.

También puede darse una definición alternativa atendiendo sólo a la frontera de P :un polígono es monótono cuando su frontera se puede descomponer en dos cadenas monótonas respecto a la misma dirección. Entendiendo por cadena poligonal monótona respecto a D si cualquier recta ortogonal a D que interseca a la cadena lo hace en un punto o en un lado.

Polígono Ortogonal Monótono

Este polígono aglutina las propiedades de los dos precedentes polígonos descritos. Es decir es tanto ortogonal como monótono.

Polígono Convexo

Un polígono P es convexo si el segmento que une dos cualesquiera de sus puntos está totalmente contenido en P. De esta forma, por ejemplo, un pentágono regular (figura izquierda) es convexo, mientras que un pentágono mellado no lo es (figura derecha). Un polígono que no es convexo se llama polígono cóncavo.

Polígono Espiral

Los ángulos de un polígono pueden ser menores que 180 (ángulos convexos) o mayores que 180 (ángulos cóncavos)Un polígono es espiral si todos sus ángulos cóncavos son consecutivos

espiral

 

No espiral

 
 

 

 

 

 

 


Visibilidad

Para tener una noción de la definición de visibilidad, nosotros podemos decir que el punto x puede ver al punto y (o y es visible por x) dentro de un polígono P, si el segmento cerrado xy no corta en ningún punto los límites del polígono P.

Problema de la Galería de Arte

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

Índice