[fusion_builder_container type=”flex” hundred_percent=”no” equal_height_columns=”no” hide_on_mobile=”small-visibility,medium-visibility,large-visibility” background_position=”center center” background_repeat=”no-repeat” fade=”no” background_parallax=”none” parallax_speed=”0.3″ video_aspect_ratio=”16:9″ video_loop=”yes” video_mute=”yes” border_style=”solid”][fusion_builder_row][fusion_builder_column type=”1_1″ layout=”1_1″ background_position=”left top” border_style=”solid” border_position=”all” spacing=”yes” background_repeat=”no-repeat” margin_top=”0px” margin_bottom=”0px” animation_speed=”0.3″ animation_direction=”left” hide_on_mobile=”small-visibility,medium-visibility,large-visibility” center_content=”no” last=”true” hover_type=”none” first=”true” background_blend_mode=”overlay”][fusion_text hide_on_mobile=”small-visibility,medium-visibility,large-visibility” sticky_display=”normal,sticky” animation_direction=”left” animation_speed=”0.3″ animation_delay=”0″]
El teorema de la Galería de Arte.
El problema fue planteado por Victor Klee en 1973, pero antes plantearemos algunas nociones sencillas.
Hablamos de galerías de arte, museos (en líneas generales, cualquier recinto), que se deben vigilar para que nadie toque ni se lleve nada.
En esta versión del problema (hay muchísimas variantes), la galería a vigilar está representada por un polígono simple (los lados de nuestro polígono no se cortan entre ellos).
El problema es decidir dónde colocar a los vigilantes/cámaras/detectores en el polígono que representa a la galería, con el fin de que toda ella quede cubierta por la mirada de éstos.
En esta primera versión del problema, los vigilantes (o cámaras, o detectores) tienen que estar situados en los vértices (esquinas) del polígono, fijos, no se pueden mover. Tienen visión de 360º y pueden ver a cualquier distancia, siempre que no haya una pared que se lo impida.
En la imagen superior se ha situado un vigilante, detector o cámara en un vértice del polígono y resaltado la zona que sería cubierta, sin moverse, suponiendo que puede ver/detectar a cualquier distancia y con una cobertura de 360º. Con estas restriccio-nes, ya podemos formular la pregunta que planteó Klee:
Dado un polígono con n vértices ¿cuántos vigilantes son suficientes para vigilar todo el polígono?
El problema que plantea Klee no es que tengamos un polígono, dibujado, con n vértices y que utilicemos el menor número de vigilantes para ese polígono en concreto.
Lo que plantea Klee es que demos una fórmula o relación, de forma que podamos saber para un número de vértices n cualquiera, cuál es el número suficiente de vigilantes para controlar esa galería, sin saber siquiera qué forma tiene la galería, sólo a partir del número de vértices que tiene el polígono que representa la planta del museo.
¿Es posible? La forma del polígono tiene mucho que ver; de hecho puede haber polígonos con muchos vértices que se vigilen con un sólo vigilante y otros que con muchos menos necesiten más de uno…
Polígono 4: Necesita, al menos, dos vigilantes.
En el dibujo anterior, tenemos una galería con n vértices que puede ser vigilada por un sólo vigilante y otra con 6 vértices, que va a necesitar dos. Entonces, ¿cómo dar un número en función del número de vértices?
La relación que encontró Chvátal en 1975, es que cualquier galería de n vértices, se puede vigilar siempre con un máximo de n/3 vigilantes. En realidad, más concretamente, con la parte entera por defecto de ese número, que se representa como [n/3].
Por ejemplo, cualquier galería de 13 vértices, sea como sea, necesitará como máximo 4 vigilantes (13/3 = 4’33333333…); de donde [N/3] = [13/3] = 4 vigilantes.
Pues bien, aunque la fórmula que relaciona el número de vértices del polígono con el número máximo de vigilantes que se necesitarían es de Chvátal, ha sido la demostración de este hecho dada por Fisk en 1978 la que más ha trascendido por su elegancia y sencillez.
Triangulación del espacio.
Lo primero que observa Fisk es que un triángulo, sea como sea, sólo necesita siempre un vigilante en uno de sus vértices. Lo que propone hacer es dividir la galería en triángulos, asegurar la vigilancia en cada unos de esos triángulos y con ello tendrá asegurada la vigilancia del polígono completo.
En primer lugar, lo que hay que hacer es triangular el polígono, añadiendo diagonales interiores uniendo vértices no consecutivos del polígono, siempre que no corten a otra diagonal ya dibujada o a la frontera del polígono.
Después vamos a asignar colores a los vértices del polígono respetando únicamente una regla: dos vértices con el mismo color no pueden estar unidos en el dibujo de la triangulación que hemos hecho del polígono. Pues bien, respetando esta regla, Fisk demuestra que se puede colorear la triangulación del polígono con 3 y sólo 3 colores.
En el ejemplo que estamos viendo, tenemos 6 vértices azules, 4 vértices rojos, y 3 vértices verdes. Elegimos el menos repetido (el verde), y colocando un vigilante en cada uno de los tres vértices verdes conseguimos vigilar todo el polígono.
¿Por qué? Porque todos los triángulos del polígono tienen que tener un vértice verde (en realidad, todos los triángulos tienen un vértice de cada uno de los colores) y como en todos los vértices verdes hay un vigilante, todos los triángulos estarán vigilados.
A partir de este teorema, sabemos que con cualquier polígono de n vértices propuesto, como máximo, vamos a necesitar [n/3] vigilantes para vigilarlo. Eso sí, hay veces que necesitaremos muchos menos, y otras en que necesitaremos exactamente [n/3].
Este problema de la Galería de Arte ha dado lugar a una inmensa cantidad de problemas geométricos, relacionados con modificar algunas de las condiciones: permi-tiendo que los vigilantes se muevan, obligando a que cada vigilante esté controlado por otro de sus compañeros en todo momento, restringiéndose a un ángulo de visibilidad (pensando en focos e iluminación), permitiendo que se atraviesen paredes, (si pensamos en detectores)…
[/fusion_text][fusion_video video=”https://www.akademik.es/wp-content/uploads/2023/07/EXPERTO-DIRECCION-DE-SEGURIDAD.mp4″ loop=”yes” autoplay=”yes” mute=”no” preview_image=”https://www.siqure.es/wp-content/uploads/2023/07/EXPERTO-DIRECCION-DE-SEGURIDAD.jpg” hide_on_mobile=”small-visibility,medium-visibility,large-visibility” box_shadow=”no” box_shadow_blur=”0″ box_shadow_spread=”0″ /][fusion_button link=”https://www.siqure.es/contacto/” target=”_self” alignment=”left” hide_on_mobile=”small-visibility,medium-visibility,large-visibility” sticky_display=”normal,sticky” color=”default” linear_angle=”180″ text_transform=”none” stretch=”default” margin_top=”10″ margin_right=”10px” margin_bottom=”10px” margin_left=”10px” icon_position=”left” icon_divider=”no” hover_transition=”none” animation_direction=”left” animation_speed=”0.3″ animation_delay=”0″]Más información[/fusion_button][/fusion_builder_column][/fusion_builder_row][/fusion_builder_container]