Problema de la galería de arte
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.
Estas galerías vigilan las colecciones con video cámaras durante las noches, se busca que el número de video cámaras sea lo más pequeño posible pero que cada parte de la galería pueda ser visible por al menos una de ellas.
Por lo tanto, la colocación de las cámaras debe ser estratégica.
Definiendo el problema, se toma un plano del lugar para dar una mejor visión de donde se pueden colocar las cámaras.
Así, se puede representar a la galería con un Polígono simple y a las posiciones de las cámaras con un punto en el polígono.
Una cámara puede observar aquellos puntos en el polígono que pueden ser conectados con un segmento abierto que se encuentre dentro del polígono.
Para definir cuantas cámaras necesita el polígono, se debe expresar una cota del número de cámaras en término del número de vértices del polígono
vértices, aunque existen casos donde dos polígonos que tienen un mismo número de vértices no pueden ser vigilados por el mismo número de cámaras.
[1][2] Esto se puede hacer mejor, buscando una estrategia para colocar las cámaras en algunas de las diagonales de los triángulos, ya que en esta posición una cámara podrá vigilar a 2 triángulos y se reduciría el número de cámaras a
, tal que cualquier triángulo en la triangulación contenga al menos un vértice seleccionado y colocar la cámara en ese sitio.
Para elegir tal subconjunto, se le asigna una 3-coloración a
, que es asignar tres colores a los vértices de
y se realiza de tal forma que cualquiera dos vértices conectados por una diagonal tienen asignado un color diferente, así cada triángulo tendrá asignado cada uno de los tres colores en sus vértices.
Por último se eligen los vértices que contienen el mismo color y que sea el color que se encuentre en un número menor de vértices que los demás colores, y se colocan las cámaras.
Esto reduce el número de cámaras a
, ya que estas cortan a la triangulación en dos, esto quiere decir que este grafo dual es un árbol.
[1] La 3-coloración se irá realizando con una Búsqueda en profundidad del árbol, manteniendo que todos los vértices de los triángulos que ya han sido visitados por la búsqueda ya han sido coloreados por cada uno de los tres colores y no existen 2 vértices conectados con el mismo color.
A continuación se muestra una propiedad para la colocación de cámaras en un polígono simple:[1][2] Teorema 1 Para un polígono simple con
cámaras son ocasionalmente necesarias y siempre suficientes para tener cada punto en el polígono visible a al menos una de ellas.
Esta teorema dice que la colocación de las cámaras no puede hacerse mejor y esto se debe a que existe una familia de polígonos simples que requieren de exactamente
Son ocasionalmente necesarias porque aunque existan polígonos simples que les basten menos de
cámaras, como el Polígono convexo, siempre va existir esta familia que no pueda reducir el número de cámaras
