Problema de la galería de arte

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 ${\displaystyle n}$ y exponer el peor escenario que puede haber, que es tener un polígono simple con ${\displaystyle n}$ 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.

Un polígono convexo puede ser vigilado con una sola cámara. Un polígono cóncavo necesita más de una.

Sea ${\displaystyle P}$ un polígono simple de ${\displaystyle n}$ vértices. Se procede a descomponer a ${\displaystyle P}$ en triángulos, esto recibe el nombre de Triangulación de un polígono. Si se coloca una cámara por cada triángulo de la triangulación se necesitarán ${\displaystyle n-2}$ cámaras, debido a un teorema de la triangulación de un polígono que menciona que cualquier triangulación de un polígono simple con ${\displaystyle n}$ vértices contiene exactamente ${\displaystyle n-2}$ triángulos. [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 ${\displaystyle n/2}$ .[1] Pero, aún se puede reducir más el número de cámaras si se colocan en algunos de los vértices de ${\displaystyle P}$ porque un vértice puede ser incidente a varios triángulos y así mismo puede vigilarlos.

La estrategia para elegir los vértices donde se colocarán las cámaras es eligiendo un subconjunto de vértices de ${\displaystyle P}$, 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 ${\displaystyle P}$, que es asignar tres colores a los vértices de ${\displaystyle P}$ 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 ${\displaystyle n/3}$ .[1]

Se comienza realizando un Grafo dual a la triangulación realizada en ${\displaystyle P}$, este grafo dual tiene un nodo por cada triángulo en la triangulación. Hay un arco entre dos nodos ${\displaystyle a}$ y ${\displaystyle b}$ si el triángulo que corresponde a ${\displaystyle a}$ y el triángulo que corresponde a ${\displaystyle b}$ comparten una diagonal. Los arcos en este grafo dual son diagonales de la triangulación de ${\displaystyle P}$, 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.

3-coloración de ${\displaystyle P}$, en una búsqueda de profundidad se va al nodo ${\displaystyle b}$ desde el nodo ${\displaystyle a}$, los vértices del triángulo de ${\displaystyle a}$ ya han sido coloreados, solo un vértice del triángulo de ${\displaystyle b}$ resta por ser coloreado, solo existe un color que queda para este vértice y es el color que no es usado por la diagonal compartida entre el triángulo de ${\displaystyle a}$ y el triángulo de ${\displaystyle b}$

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 ${\displaystyle n}$ vértices, ${\displaystyle n/3}$ 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 ${\displaystyle n/3}$ cámaras para poder ser vigilados, esta familia consiste de un polígono simple en forma de peine.

polígono simple en forma de peine con cámaras, ${\displaystyle n=12}$ cada diente del peine necesita ser vigilado por una cámara y justo se tienen ${\displaystyle n/3}$ dientes

.

Son ocasionalmente necesarias porque aunque existan polígonos simples que les basten menos de ${\displaystyle n/3}$ cámaras, como el Polígono convexo, siempre va existir esta familia que no pueda reducir el número de cámaras ${\displaystyle <n/3}$, pero por otro lado siempre son suficientes porque para todas las familias de polígonos simples siempre va a bastar tener ${\displaystyle n/3}$ cámaras.