Georgy Voronoi (1868-1908) fue un matemático soviético, famoso por el estudio en profundidad en n dimensiones de los diagramas a los que finalmente se les ha dado su nombre. En inglés se suele usar la expresión "diagram of Voronoi", mientras que en castellano es más habitual expresarlo por regiones de idem. ¿En qué consisten? Aquí @clara_grima los definió perfectamente:
Consiste en dividir el espacio en tantas regiones como puntos u objetos tengamos de tal forma qu ea cada punto le asignemos la región formada por todo lo que está más cerca de él que de nadie
Y abusando de su confianza, voy a emplear la misma imagen como ejemplo:
Es un problema de geometría computacional, y habitualmente se ha empleado para problemas relativos a cómo repartir el espacio. Por ejemplo, en qué puntos de una ciudad poner buzones/farmacias. Aunque también nos podemos encontrar esta imagen en la naturaleza o en la arquitectura.
Y no solo eso, sino que las regiiones de Voronoi están de moda en el campo de la robótica, gracias a la creación de "carreteras" para estos aparatos (robotic roadmaps). Me explico: imaginaos que tenemos un escenario con obstáculos. Normalmente, en robótica se trata de hallar el algoritmo más eficiente para ir de un punto a otro (ya sea por ser el más corto o el que menos energía requiere). Pero los obstáculos no se pueden saltar de cualquiera manera.
Lógicamente, Voronoi por sí solo no permite hallar el camino de un punto A a B, sino que para eso hace falta alguna otra herramienta, como el algoritmo de Djikstra, y un posterior suavizado de las esquinas de Voronoi.
Y ojo, porque Georgy Voronoi no fue el primero que usó estas regiones, sino que fue el primero que lo estudió en profundidad. Anteriormente, en el siglo XVII ya los usaba Descartes.
Sin embargo, da igual la aplicación para la que queramos esta curiosidad geométrica: es un poco complicado obtenerla desde 0. El algoritmo más habitual para conseguirlo es el que propuso Steven Fortune en 1986, quien formaba regiones de Voronoi a partir de lo que parece la línea del mar entrando en la arena.
Pero hablar de Fortune me estropearía el artículo. La manera que os presentaré para crear las regiones de Voronoi son los famosos triángulos de Boris Delaunay (1890-1980), quien también fue un matemático soviético. Delaunay lograba repartir una nube de puntos en triangulaciones especiales, ya que los vértices de los triángulos de Delaunay siempre son parte de una circunferencia que no contiene ningún otro punto de esa nube.
Y además, resulta que la estructura de Delaunay es el grafo dual de Voronoi, y a partir de uno se puede conseguir el otro, aunque no entraré en esos detalles. En la siguiente imagen, el trazo oscuro corresponde a Delaunay, mientras que el discontinuo a Voronoi.
Pero de nuevo, aunque esto naciera como el estudio de una curiosidad geométrica, la triangulación de Delaunay sirven por sí mismas en aplicaciones muy actuales. Una de ellas, es el empleo de estas estructuras en creación de imágenes de cine a partir de sistemas de captura de movimientos. Es así tal y como se grabó la famosa película Avatar, en muchos vídeo-juegos actuales o en el archiconocido Gollum, de El Señor de los Anillos. Cierto es que junto a triangulaciones de Delaunay se emplearon otro tipo de técnicas.
Este vídeo, aunque sea bastante casero, muestra un ejemplo de triangulación a partir de una imagen real. Por cierto, fue Delaunay quien estrictamente se apoyó en Voronoi, para entre otras cosas, sentar las bases matemáticas de la cristalografía.
Por lo tanto, espero que este artículo sea uno de mis pequeños granos de arena para demostraros que:
a) las matemáticas están en todas partes y sirven
b) no podemos predecir dónde se aplicarán los descubrimientos o trabajos científicos
c) la interrelación entre disciplinas hoy en día es total
0 comentarios:
Publicar un comentario