Problema de la galería de arte

El problema de la galería de arte o problema del museo es un problema de visibilidad muy estudiado en 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.

La motivación de este problema se da porque las galerías de arte tienen que vigilar sus valiosos cuadros de pintores famosos para evitar que los criminales intenten robarlos. Estas galerías vigilan las colecciones con cámaras de vídeo durante las noches, y se busca que el número de cámaras sea lo más pequeño posible, pero que cada parte de la galería pueda ser visible desde al menos una de ellas. Por lo tanto, la colocación de las cámaras debe ser estratégica.^[1]

Definición

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

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 la galería mediante un polígono simple, y las posiciones de las cámaras con un punto en el polígono. Una cámara puede observar aquellos puntos del polígono que pueden ser conectados con la posición de la cámara mediante un segmento que se encuentre totalmente 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 función del número de vértices del polígono $n$ y exponer el peor escenario que pueda darse, que es tener un polígono simple con $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.

Sea $P$ un polígono simple de $n$ vértices. Se procede a descomponer $P$ en triángulos, proceso que 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 $n-2$ cámaras, debido a un teorema que establece que cualquier triangulación de un polígono simple con $n$ vértices contiene exactamente $n-2$ triángulos.^[1]^[2]

Esta solución se puede mejorar, 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 $n/2$ .^[1] Pero todavía se puede reducir más el número de cámaras si se colocan en algunos de los vértices de $P$ , porque un vértice puede formar parte de varios triángulos, y en consecuencia, puede divisarlos por completo.

Colocación de las cámaras de vigilancia

La estrategia para determinar los vértices donde se colocarán las cámaras es eligiendo un subconjunto de vértices de $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 $P$ , lo que consiste en asignar tres colores distintos a los vértices de $P$ , lo que se realiza de tal forma que cualquier par de vértices conectados por una diagonal tienen asignado un color diferente. Así, cada triángulo tendrá asignado los tres colores en cada uno de 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 en ellos las cámaras. Esto reduce el número de cámaras a $n/3$ .^[1]

3-coloración de un polígono simple

3-coloración de $P$ : mediante una búsqueda en profundidad, se va al nodo $b$ desde el nodo $a$ , los vértices del triángulo de $a$ ya han sido coloreados, solo un vértice del triángulo de $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 $a$ y el triángulo de $b$

Para colorear los vértices, se comienza realizando un grafo dual de la triangulación creada en $P$ . Este grafo dual tiene un nodo por cada triángulo que forma parte de la triangulación. Hay un arco entre cada dos nodos $a$ y $b$ si el triángulo que corresponde a $a$ y el triángulo que corresponde a $b$ comparten una diagonal. Los arcos en este grafo dual son diagonales de la triangulación de $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 que no existen 2 vértices conectados entre sí con el mismo color.

Propiedades

Polígono simple en forma de peine con $n=12$ cámaras de vigilancia: cada diente del peine necesita ser vigilado por una cámara y justo se tienen $n/3$ dientes

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 $n$ vértices, $n/3$ cámaras son ocasionalmente necesarias y siempre serán suficientes para tener cada punto en el polígono visible en 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 $n/3$ cámaras para poder ser vigilados. Esta familia es un polígono simple con forma de peine. Se dice que son al menos necesarias porque aunque existan polígonos simples a los que les basten menos de $n/3$ cámaras, como en el caso de los polígonos convexos, siempre va existir esta familia en la que no se pueda reducir el número de cámaras de vigilancia a $<n/3$ . Pero por otro lado, siempre son suficientes, porque para todas las familias de polígonos simples siempre va a bastar tener $n/3$ cámaras.

Referencias

↑ ^a ^b ^c ^d ^e ^f de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark. Computational Geometry Algorithms and Aplications (3 edición). Springer. ISBN 978-3-540-77973-5. |fechaacceso= requiere |url= (ayuda)
↑ ^a ^b O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. p. 350. |fechaacceso= requiere |url= (ayuda)

Datos: Q2000090
Multimedia: Art gallery problem / Q2000090

[MarkdeBerg-1] ↑ ^a ^b ^c ^d ^e ^f de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark. Computational Geometry Algorithms and Aplications (3 edición). Springer. ISBN 978-3-540-77973-5. |fechaacceso= requiere |url= (ayuda)

[Orourke-2] O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. p. 350. |fechaacceso= requiere |url= (ayuda)

[1]

[2]