Entradas etiquetadas como ‘Geometría Computacional’

¿Cuántos nos están vigilando?

La semana pasada la terminamos con una noticia tan gratificante como ésta. Y una se plantea ¿quién está decidiendo nuestros destinos? ¿Quién está dibujando el futuro de nuestras familias? ¿Cuántos nos están vigilando? Y porque sospecho, digo sospecho, que también nos vigilan desde ese polígono de 5 vértices, el Pentágono, se me ha venido a la cabeza uno de mis problemas favoritos de Geometría Computacional que mezcla esos dos conceptos, vigilancia y polígonos: El problema de la Galería de Arte.  Aparte de la belleza intrínseca de este problema, de la que intentaré convenceros a lo largo de esta entrada, mi debilidad por él tiene un origen romántico: fue el primer problema de esta disciplina que leí y que me atrapó en las redes de esta forma de hacer Matemáticas.

¿Cuál es el Problema de la Galeria de Arte?

El problema fue planteado por Victor Klee  en 1973, pero antes de plantearlo, dejadme que demos algunas nociones muy sencillitas. Vamos a hablar de galerías de artes, museos, que tenemos que vigilar para que nadie toque ni se lleve nada. Pues bien, para nosotros, en esta versión del problema que vamos a contar (hay muchísimas variantes), la galería que queremos vigilar estará representado por un polígono simple, y cuando decimos simple lo que queremos decir es que los lados de nuestro polígono no se cortan entre ellos, voy a hacer un dibujo por si se ve más claro.

Seguimos.  Cuando decimos que queremos vigilar la galería de arte, lo que queremos es decidir dónde colocaremos a los vigilantes 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 tienen que estar situados en los vértices (esquinas) del polígono, fijos, no se pueden mover. Tienen visión de 360ª y no son miopes, es decir, pueden ver a cualquier distancia, siempre que no haya una pared que se lo impida. A ver, voy a hacer otro dibujo por aquello de que  una imagen….

En la imagen superior, hemos situado un vigilante en un vértice del polígono y hemos sombreado la zona que sería cubierta por éste, sin moverse, suponiendo que puede ver a cualquier distancia y 360º a la redonda.  Con estas restricciones, ya podemos plantear la pregunta que planteó Klee:

Dado un polígono con N vértices ¿cuántos vigilantes son siempre suficientes para vigilar todo el polígono?

Ahora bien, el problema que plantea Klee no es que nos dan un polígono, dibujado, con N vértices y que nosotros coloquemos 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ántos guardianes serán suficientes para vigilar esa galería, sin saber siquiera qué forma tiene la galería,  sólo a partir del numero de vértices que tiene el polígono que representa la planta del  museo. Pero, ¿eso como va a ser? 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… Otro dibujo nos vendrá bien.

En el dibujo anterior, tenemos una galería con 13 vértices que puede ser vigilada por un sólo guardián y otra con 6 vértices, que va a necesitar 2. Entonces, ¿cómo vamos poder dar un número en función del número de vértices? Si pensamos en un hexágono regular, podemos entender que será vigilado con 1 sólo vigilante, y el polígono de 6 lados de nuestra anterior figura necesita 2, ¿cómo vamos a encontrar esa fórmula?

Pues sí, se encontró. Bueno,  la relación que encontró Chvátal en 1975, es que cualquier galería de N vértices, sea como sea, con la forma que sea, por muy enrevesado que sea el Calatrava de turno,  se puede vigilar siempre con N/3 guardianes. En realidad, más concretamente, con la parte entera por defecto de ese número, que escribimos así ⌊N/3⌋, esto es, que si N/3 no nos sale un número natural, sino que sale con decimales, nos quedamos con ése mismo número pero sin decimales, nada de poner trozos de vigilantes, eso lo dejamos para Dexter y otros como él. Por ejemplo, cualquier galería de 13 vértices, sea como sea, necesitará como máximo, 4 vigilantes (13/3 = 4’33333333…) Que sí, que la del último dibujo necesita sólo 1, vale, pero no es posible encontrar ninguna que necesite más de 4, eso es lo que nos asegura el Teorema de la Galería de Arte de Chvátal. Eso y que siempre es posible encontrar un polígono de N vértices que necesite exactamente ⌊N/3⌋ guardianes.

Pues bien, aunque el mérito de encontrar la fórmula que relacionara el número de vértices del polígono con el número máximo de guardianes que se necesitarían para vigilarlo 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. Tanto que ha sido una de las elegidas para aperecer en el Libro de las Demostraciones del que tanto hablaba Erdős y del también hablamos aquí.

Vamos a contar la demostración de Fisk porque es concisa, sencilla, brillante y hermosa.

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, ¿verdad? Pues 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. Vamos allá…

En primer lugar, lo que hay que hacer es triangular el polígono ¿Cómo? 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.

Ahora 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.

Venga. Ahora contamos cuántos vértices hay de cada uno de los 3 colores en la triangulación del polígono. En el ejemplo que estamos haciendo en nuestro cuaderno, tenemos 6 vértices azules, 4 vértices rojos, y 3 vértices verdes. Elegimos el color menos popular de los 3, en esto caso el verde, y colocamos un vigilante en cada uno de los 3 vértices verdes y ¡tachán! Ya está todo el polígono vigilado ¿Por qué? Pues 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.

Sí, es maravillosa la demostración. Yo también me quedé boquiabierta la primera vez que la leí.

Bueno, nos queda apuntar un detalle ¿Cómo sabemos que el color menos popular de la triangulación siempre aparece como máximo ⌊N/3⌋ veces? Pues por el Prinicipio del palomar. Supongamos que los vértices son palomas y los colores, 3 palomares. Asignar colores a los N vértices se puede interpretar como asignar las N palomas a uno de los 3 palomares. Pues ya está, uno de los 3 palomares como mucho, tiene N/3 palomas. Porque si los tres tuvieran más de N/3 palomas, la suma de las 3 cantidades sería superior a N.

Lo que sabemos entonces a partir de este teorema es que sea como sea el polígono de N vértices que nos propongan, como máximo, vamos a necesitar ⌊N/3⌋ vigilantes para vigilarlo. Eso sí, hay veces que necesitaremos muchos menos, y otra 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, simplemente con modificar algunas de las  condiciones: permitiendo 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 routers)… Todos problemas muy sencillos de plantear pero la mayoría muy difíciles de resolver.

Lo dejamos por aquí y espero que haya servido para olvidar durante un rato cuántos y quiénes son los que nos están vigilando a todos nosotros…

Un niño grande que juega con papel

Cuando dices que eres investigadora en el área de Matemáticas no es difícil que alguien te pregunte ¿aún quedan cosas por descubrir en Matemáticas? ¿No está todo descubierto? Es entonces cuando tratas de explicar, sin palabros, que efectivamente no, no está todo descubierto y que, aparte de los problemas matemáticos clásicos planteados por ilustres matemáticos y que aún siguen sin resolver desafiando a las mentes que se dedican a ello, el desarrollo de la informática y las nuevas tecnologías hace imprescindible el avance de esta disciplina en la resolución de nuevos problemas, problemas sobre todo de tipo computacional. En ese sentido, por ejemplo, entre otras áreas, se encuentra la Geometría Computacional. Es ahora cuando me toca explicar qué es la Geometría Computacional, y aunque traté en su tiempo de hacerlo en esta entrada que publiqué en Gaussianos, tras una invitación del editor del mismo y he tratado de convencer de la belleza y versatilidad de sus estudios en dos entradas de Amazings.es, una primera explicando las aplicaciones del Diagrama de Voronoi y en la segunda parte, mostrando algunas estrategias de la materia para resolver el problema del cálculo del Diagrama de Voronoi, en pocas palabras, se podría decir que la Geometría Computacional se ocupa de tratar de resolver problemas de naturaleza geométrica, pero con métodos que puedan ser entendidos por un ordenador, y hacerlo de la forma más rápida (con menos operaciones) posible.

 

Erik y una de las autoras del blog

Erik Demaine no sólo investiga y publica en este área, pero es sin duda en la que más ha participado y gracias a lo cual he tenido el placer de conocer. Este niño grande, curioso y sorprendentemente brillante, fue con  20 años, el profesor más joven del prestigioso  Instituto de Tecnología de Massachusetts, M.I.T, o  emaití, como se le llama a veces coloquialmente

¿Con 20 años? ¿Sólo con 20 años?

Pues sí, porque aunque Erik detesta que se le tache de niño prodigio, no ha podido evitar ser incluido, por ejemplo, en esta lista, ni ser presentado como tal en la multitud de entrevistas y notas de prensa que sobre él se han publicado desde que era pequeño.

Erik nació en 1981 en Halifax (Canadá), su padre Martin Demaine es una figura capital en su formación ya que pronto se estableció una relación muy especial entre ambos. Cuando Erik tenía sólo 6 años, ambos fundaron la Erik and Dad Puzzle Company una compañía que se dedicaba a elaborar puzzles y pasatiempos. Un año más tarde, padre e hijo decidieron llevar una vida nómada por Estados Unidos y Canadá.  El padre era un artista y artesano, sobre todo trabajaba y trabaja el vidrio (ahora  como científico en un equipo de investigación del citado MIT, en  proyectos que conectan el arte con las matemáticas).

Esta vida nómada  les permitía ir de feria en feria, así  que Martin decidió dar clases a Erik usando unos manuales de una agencia especializada en la enseñanza no escolarizada. Pronto Erik superó a su padre en muchas materias y a partir de los nueve años fue prácticamente autodidacta hasta que a la edad de 12 años entró en la universidad, consiguiendo titularse a los 14. Obtuvo su  doctorado  con 20 años y con esa misma edad, como ya se ha dicho, fue el catedrático más joven en la historia del MIT.

Una de las autoras del blog con el padre de Erik, Martin Demaine

En realidad, a la vez que le ofrecían la plaza a Erik, el propio MIT hizo una oferta a Martin, así padre e hijo pudieron seguir trabajando juntos. La labor de ambos está centrada en varios campos como son el arte (donde el padre juega un papel principal), las matemáticas y la informática. Además han conseguido que confluyan estas tres disciplinas cuando han estudiado las matemáticas asociadas al arte del origami (papiroflexia), campo en el que son reconocidos expertos mundiales, incluso tres de sus obras han entrado a formar parte de la colección permanente del Musseum of Modern Art de Nueva York (MOMA). Pero si la vertiente artística de los trabajos de los Demaine es evidente a partir de las imágenes de sus creaciones en papel, el desarrollo por parte de Erik de esta nueva especialidad, el Origami Computacional, es mucho más que eso. Se trata de un esfuerzo interdisciplinar a caballo entre Matemáticas e Informática. Su interés se centra, principalmente, en problemas relacionados con la geometría asociada al plegado de papel con aplicaciones prácticas  en campos tan diversos como la manufacturación industrial (fabricación de láminas de metal, bolsas de aire, envoltorios de caramelos), Física (nanoestructuras), o  Biología (plegamiento de proteínas).

Erik confiesa que su interés por las matemáticas surgió a partir de los videojuegos. Su padre le comentó que para programar videojuegos tenía que aprender lenguajes de programación y ser bueno en matemáticas y le proporcionó algunos libros empezando por álgebra lineal. En realidad nunca ha abandonado su pasión por los videojuegos y ello le llevo a probar que el juego de Tetris pertenece a la categoría de juegos muy difíciles (es NP-duro encontrar una estrategia ganadora).

Pero además de una mente realmente prodigiosa. Erik es un tío optimista y travieso que disfruta de su trabajo y quiere hacer partícipes a todos de ese goce supremo. No pierde ocasión de bromear sobre hechos matemáticos, como se puede apreciar por ejemplo en esta vídeo en el que, coincidiendo con la celebración del April Fools’ Day (día de las inocentadas), demuestra que P=NP, sufriendo unas terribles consecuencias…

Por último, si se preguntan por qué en todos los congresos la charla de los Demaine e una de las más concurridas de todas, no dejen de ver este vídeo donde además ellos mismos hablan de su historia y hacen… bueno, es mejor que lo vean 😉

Eso sí, este niño grande y brillante es un racionalista incondicional…

There’s nothing Science can’t prove.

Erik Demaine