Cada uno en su región y Voronoi en la de todos

Diseño de | Raquel Garcia

Estudié matemáticas, sí, por lo de la belleza suprema, ya saben, a cada uno le da por algo.

Pues bien, todo son risas y geometría computacional hasta que la profesora de tu vástago te pide que vayas a clase a contarle a los niños de 3 años a qué te dedicas.

Claro que existe la opción de decirles que eres profesora, como su ‘seño’ y que enseñas cosas de los números y de los triángulos, cuadrados y círculos. Pero no es eso lo que hago, ¡eso es mucho más difícil!.

Así que, entendiendo que los niños tienen muy clara la proporción directa entre proximidad y pertenencia, me lié la manta a la cabeza y decidí hablarles sobre Diagramas de Voronoi (contando con la experta e inestimable colaboración del padre de la criatura, mi santo, matemático también).

¿Qué es un diagrama de Voronoi?

Pues… es una descomposición de un espacio métrico en regiones, asociada a la presencia de objetos, de tal forma, que en dicha descomposición, a cada objeto se le asigna una región del espacio métrico formada por los puntos que son más cercanos a él que a ninguno de los otros objetos.

Lo que se dice 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.

Por ejemplo, si tenemos un conjunto de 8 puntos en el plano euclídeo,  su diagrama de Voronoi es una partición del plano de este estilo:

Ante la presencia de un nuevo punto, por ejemplo, el verde en la siguiente figura, es inmediato reconocer cuál de los 8 originales es el más cercano a él. El punto generador de la región en la que ha caído.

Esta propiedad del Diagrama de Voronoi tiene aplicaciones inmediatas, tales como encontrar el ‘restaurante’ de comida rápida de alguna famosa cadena más cercano a tu ubicación, por ejemplo, si andas de paseo por París

Pero, claro, ésta no es la forma, posiblemente, de plantearlo en la clase de tres años. Para ellos lo planteamos como una cuestión de propiedad de caramelos.

«Imaginaos» les dije «que los Lunnis están en el patio del recreo, cada uno en un sitio. Y que de pronto, alguien descubre un caramelo, como en esta figura»

«¿De quién es ese caramelo?»

Como era de esperar todas las respuestas fueron inducidas por la ley  de ‘del que esté más cerca’. Pero había dudas entre Lucho (el amarillo), Lublú (el azul) y Lubina (la bruja), que eran los tres más próximos.

Era mi momento.

El diagrama de Voronoi sirve para dividir el patio en regiones, de forma que cada Lunni sabrá que todo lo que esté en su región está más cerca de él que de ninguno de sus amiguitos.

«Vamos a construir el diagrama de Voronoi del patio de los Lunnis, a ver quién se queda el   caramelo»

«¡De Lucho!» gritaron todos, algunos arriesgando las paredes de las venitas de sus cuellos. Luego seguimos ‘lanzando’ caramelos en distintas regiones y ellos gritando el nombre del agraciado.

No sé si alguno recuerda algo de aquel día, pero parecían pasárselo bien.

Ahora bien, aparte de resolver conflictos en el patio de un colegio o de orientarte en la búsqueda de una hamburguesa, ¿qué son y para qué se utilizan los diagramas de Voronoi?

En primer lugar, dejadme que os cuente que esta estructura que recibe el nombre de Georgy Voronoi, matemático ruso, también es conocida con los nombres de Polígonos de Thiessen (en honor de Alfred Thiessen, meteorólogo estadounidense) o Teselación de Dirichlet (por el matemático Gustav Lejeune Dirichlet). Y seguro que muchos más, puesto que es una estructura tan lógica e intuitiva que aparece cada vez que uno se plantea cuestiones relacionadas con problemas de proximidad.

Pero aunque mi contacto con los diagramas de Voronoi está ligado al estudio de Geometría Computacional, disciplina relativamente joven, hay autores que señalan el uso de la citada estructura en trabajos de Descartes de 1644 sobre el cielo, cuando afirmaba que el Universo estaba plagado de éter y materia y  formado por vórtices.

Eso sí, sin duda, desde el punto de vista histórico, una aplicación del diagrama de Voronoi digna de mención, aparece en el análisis de John Snow, para muchos el padre de la epidemiología moderna, del brote cólera que azotó Londres en 1854.

Por aquel entonces  no se conocía con exactitud la etiología ni el método de trasmisión de la citada enfermedad, y se debatían entre dos posibilidades: el contagio por contacto con el enfermo, sus ropas y/o pertenencias; y la teoría miasmática que atribuían la trasmisión a condiciones atmosféricas, como los vientos. Snow usó el método geográfico deduciendo que la causa de la enfermedad era el consumo de aguas contaminadas por heces. Para ello, en un mapa, señaló la distribución de muertes por cólera.

A continuación, estudió la distribución de las fuentes de agua potable de la ciudad y delimitó las regiones de Voronoi de cada una de esas bombas. Calculando la distancia entre la residencia de cada difunto y la bomba de agua más cercana, llegó  a la conclusión de que la zona afectada más por el cólera correspondía con la región de Voronoi asociada a la bomba de Broad Street, ya que   en su región se dieron 73 de 83 casos.

Tras retirar la manija de la citada bomba, el brote de cólera se extinguió. Ea, para que digan que las matemáticas no sirven para nada… Eso sí, Snow no le llamaba regiones de Voronoi por varias razones, entre otras, porque Voronoi no había nacido.

Desde entonces y hasta nuestros días, el diagrama de Voronoi en 2 y 3 dimensiones ha sido utilizado en campos muy diversos. Vamos a ver algunos de ellos.

Fijaos que por ejemplo, en Robótica, si tenemos una escena con obstáculos  en las que un robot deba moverse, una forma de evitar las colisiones sería diseñar la trayectoria del robot sobre las líneas del diagrama de Voronoi  de los obstáculos, con lo que se movería siempre a medio camino entre dos de ellos.

Fuente | Imagen

En la figura anterior, los obstáculos, en rojo, y las líneas punteadas azules, los límites de las distintas regiones de Voronoi de los mismos (sí, también se puede calcular el diagrama de Voronoi de otros objetos que no sean puntos). Si el robot camina por las líneas azules, no habrá colisión.

Esta misma estrategia podría ser utilizada en diplomacia para ‘pasear’ entre intereses enfrentados sin dar lugar a suspicacias, pero no me consta que esté muy afinado el algoritmo…

Una idea similar a la del robot, se propone en un trabajo de C.M. Gold de 2006, planteando el uso de esta misma estructura en el ámbito de sistemas de información geográfica, utilizando, de nuevo, las aristas del diagrama para evitar la colisión con los accidentes geográficos.

fuente | Imagen

Otra aplicación de este diagrama, por ejemplo, es el cálculo del mayor círculo vacío.

Imaginemos que los puntos representan núcleos urbanos y que queremos ubicar un servicio indeseable, algo que nadie quiere tener cerca, no sé, por ejemplo, una central nuclear, una fosa de purines o una hamburguesería de alguna cadena popular. Hombre, siempre está la alternativa de mandarla al país vecino, pero eso no está bonito. Vamos a restringir el problema, el servicio indeseado, hay que ubicarlo dentro de la envolvente convexa de los núcleos de población. De manera intuitiva, la envolvente convexa de un conjunto de puntos en el plano, es la forma que adoptaría una goma elástica si la soltáramos alrededor de los puntos, en los que hemos calvado puntillas, en la siguiente figura la tenemos en verde:

Observad que los puntos que están sobre la envolvente convexa (en verde) tienen regiones de Voronoi no acotadas, abiertas. Esta propiedad es útil muchas veces, y no tanto otras como se verá más adelante.

(Sobre el cálculo de la envolvente convexa y la filosofía de la Geometría Computacional escribí hace un tiempo esto para Gaussianos)

En ese caso, para ubicar un servicio chungo dentro de la frontera verde, lo que tenemos que conseguir es que la población más cercana a dicho servicio esté lo más alejada posible de el mismo, es decir, maximizar la mínima distancia a él. Esto se consigue ubicándolo en el centro del mayor círculo vacío de poblaciones que podamos dibujar dentro de la frontera verde. Pues bien, ¡tachán!, ese círculo estará centrado en un vértice del diagrama de Voronoi.

Interesante, ¿no? Pues no se vayan todavía, aún hay más.

Vámonos al bosque. Porque también se ha usado el diagrama de Voronoi como herramienta de investigación forestal para analizar y predecir la influencia del espacio ocupado por los árboles en la evolución de un bosque. Mi colega y amigo Manuel Abellanas de la Universidad Politécnica de Madrid, junto a otros investigadores, ha desarrollado VOREST, la herramienta mencionada.

Eso a nivel macroscópico, pero también a nivel microscópico podemos encontrar trabajos que aplican el diagrama de Voronoi a sus investigaciones. Ya desde 1974, F.M. Richards, biólogo estructural en  Yale e innovador en el estudio de las relaciones entre las estructuras de proteínas y sus funciones biológicas, señaló la eficiencia y relevancia de nuestra estructura en 3 dimensiones para la descripción de la estructura de las proteínas.

Entre los numerosos trabajos que podemos encontrar en esa línea, tenemos, por ejemplo, esta herramienta, VORO3D, que permite la visualización en tres dimensiones de la estructura de las proteínas. Para ello, y hablando sin mucho rigor, considera el empaquetamiento de aminoácidos, de forma que cada residuo es representado como un punto del espacio. Como los aminoácidos cercanos a la superficie de la proteína podrían dar lugar a regiones de Voronoi abiertas, se considera la molécula dentro de un recubrimiento de esferas cuyo volumen no difiera demasiado del volumen medio real.

Representación con VORO3D de beta-purotionina

También en Química Computacional, el método de Voronoi Deformation Density (VDD) se usa para calcular la distribución de carga atómica en una molécula, para obtener información sibre sus propiedades químicas.

¿Qué más?

Los huesos. Sí, señor.  A grandes rasgos, en nuestros huesos podemos distinguir dos zonas diferenciadas: el hueso compacto y el hueso esponjoso o trabecular.

Fuente | Imagen

Existen una importante cantidad de trabajos enfocados a  generar modelos en 2 dimensiones que representen la arquitectura trabecular de los huesos, usando diagramas de Voronoi, tomando como puntos en este caso, los centros de los poros del hueso esponjoso.

Fuente | Imagen

Pero aparte de la utilidad de este tipo de estructuras, no me negaréis la belleza y armonía geométrica de las mismas. Belleza que no parece haber pasado desapercibida par arquitectos y diseñadores:

Fuente | Imagen

¿Una ciudad dentro del rascacielos Voronoi?

Fuente | Imagen

Pero un concepto tan natural e intuitivo como éste, el de vecindarios alrededor de algún punto destacada por alguna razón, debe ser encontrado también en la naturaleza, ¿no?

Cuando encuentro formas similares en el ámbito natural me gusta jugar a pensar qué puntos son los generadores de esos posibles diagramas de Voronoi, qué tienen de especial para aglutinar a otros en sus proximidades.

¿Algunos  pelos más gordotes que el resto?

¿Los últimos puntos con algo de humedad?

¿Los puntos más calientes de la superficie del Sol?

¿O el último trozo de hielo?

Tengo que parar en algún momento, pero hay infinidad de aplicaciones prácticas y motivos naturales relacionados con los diagramas de Voronoi. Están ahí fuera, esperando  que los descubráis, ¿a qué esperáis?

Ya me iréis contando, estaré por aquí. O por allí.

PD: Esta entrada participa en la Edición 2.9 del Carnaval de Matemáticas, cuyo anfitrión es el blog Que no te aburran las M@TES.

117 Comentarios

Participa Suscríbete

Pablo J Rodriguez

Me ha encantado, me parece estupenda la explicación de los diagramas de Voronoi, tan fácil que hasta yo la he entendido. jeje.
¡Así se enseña matemáticas!.

Alberto A.L.Alberto A.L.

¿Y qué es la matemática, sino el esfuerzo humano de etiquetar el universo? Bravo, un articulo que te atrapa. Muchas gracias por tu post.

JoseJose

Un uso añadido más: en la representación de constelaciones para las comunicaciones digitales.

Yester William QuebradaYester William Quebrada

Intentaremos aplicarlo al terreno de un campo de fútbol durante el desarrollo de un partido. Con ello podríamos evaluar el énfasis del uso del espcio del equipo contrario, la optimización del nuestro y el grado de dominio territorial durante todo el partido o durante un instante.

Gastón NúñezGastón Núñez

Muy buen artículo, una correción menor: La foto no corresponde a Georgy Voronoi, es una foto de Bertrand Russell.

LeandroLeandro

excelente!!!! imrpesionante como aparece en la naturaleza, y cuanto tenemos por aprender de esta!!!!
me recuerda a temas como el rectangula aurea, la secuencia fibonacci, etc
me apasiona!
gracias!

jesus patraca

Es muy cierto lo dichoe n este escrito, voronoi esta dodne sea, y es apasionante e incluso un poco escalofriante cuando de pronto por alguna clase o algun taller que tomas, vez a voronoi donde sea y en formas organicas naturales sin toque del ser humano…. y despues verlas en las distribuciones de “plato roto” en urbanismo que en realidad deberian ser: distribucion “voronoi” urbanista

javijavi

Me recuerdan a un proyecto que realice en la universidad de un forjado reticular con los pilares distribuidos irregularmente. Es exactamente igual que el area de influencia de cada pilar

Francis MurilloFrancis Murillo

Muchisimas felicidades, las matematicas nunca me habian parecido tan interesantes! estudio arquitectura y estaba buscando como abordar el tema de voronoi, sin duda me has iluminado! gracias!

Arturo Obregón RuizArturo Obregón Ruiz

Felicidades ! Excelente artículo. Después de su lectura nos cambia la percepción de muchas cosas…

Alberto IribeAlberto Iribe

Excelente explicacion como dices hasta para niños de 3 años, y como mencionan algunos asi es sencillo aprender matematicas y enseñarlas

JavierJavier

No sé cómo he llegado a este post, pero, creo que por primera vez en mi vida, he entendido y disfrutado con una explicación sobre matemáticas. Gracias!!

Enrique Valles

Muy clara tu explicación, a mi me agrada crear graficos vectoriales utlizando un script para formas Voronoi, He puesto un enlace a este articulo desde mi blog, espero no haya problema con ello.

Francisco J. GutiérrezFrancisco J. Gutiérrez

Excelente artículo. Agrego éste sitio a favoritos para de vez en cuando mirar que nuevas explicaciones nos traes. Buen trabajo

Gracias

DavidDavid

Llegué al artículo a través del que escribiste sobre geometría computacional en Gaussianos. Cada vez siento más que no tengamos una optativa en la facultad en la que estudiemos esta temática. Muchas gracias por el aporte y felicidades por la clara explicación.

DiegoDiego

Clara, una pregunta. Tu dices “me gusta jugar a pensar qué puntos son los generadores de esos posibles diagramas de Voronoi”.
La construcción de uno de estos diagramas a partir de un conjunto de puntos es muy sencilla, pero ¿Cualquier partición hecha con polígonos es un diagrama de Voronoi de un conjunto de puntos?; quiero decir, ¿la correspondencia es biunívoca? ¿siempre existen esos puntos? Una primera intuición, pobre, sin cultivar, me dice que seguramente no, al menos no solamente con puntos aislados; trato de encontrar un contraejemplo sencillo para confirmar mi intuición pero no lo hallo tampoco.
Gracias.

Marcel Chow MartínezMarcel Chow Martínez

Hola Clara.. caí en tu blog buscando precisamente información de teselación de Voronoi.. estoy tratando de encontrar propiedades a ser calculadas sobre la estructura a gran escala en el universo, más precisamente, las propiedades que podriamos extraer de la distribucion 3d de cúmulos de galaxias aplicando una teselación de Voronoi sobre estas. Me interesa mucho lograr calcular el volumen dentro de cada celda individual de Voronoi. He utilizado varios algoritmos disponibles en R, para calcular la triangulacion 3d de Delaunay, y encontrar los vertices de Voronoi para cada punto de mi muestra. Para encontrar el volumen de la celda individual, he pensado que el volumen de la envolvente convexa obtenida usando los vertices de Voronoi para una celda individual debe ser igual al volumen mismo de la celda,.. lo que para mi es muy intuitivo, pero, por supuesto, no estoy real y completamente seguro de esto. ¿Es posible que pudieras ayudarme a resolver este dilema, o qué pudieras indicarme donde buscar información al respecto? Quedaria sumamente agradecido..
Gracias..

AlbertAlbert

Hoy sale en todos los diarios que un grupo de físicos ha conseguido una simulación del universo a lo largo de los últimos 13.000 millones de años muy realista, por ejemplo ver aquí:
http://sociedad.elpais.com/sociedad/...218642.html
Se me ha ocurrido hojear el paper original que es este, para ver cómo lo habían hecho:
http://arxiv.org/ftp/arxiv/papers/14...05.1418.pdf
Clara, me he acordado enseguida de tí cuando he leído en la página 26:
“Our simulation code, AREPO, uses an unstructured Voronoi tessellation of the simulation volume, where the mesh-generating points of this tessellation are moved with the gas flow”
¡¡¡ VORONOI !!! Gracias a tí Clara aprendí el significado de esa palabra en este post, no lo olvidaré

Gloria RodriguezGloria Rodriguez

Hola, es una excelente explicacion sobre los diagramas de voronoi, me parece interesante la forma tan clara que los explicas.

Sara

Qué maravilla de articulo! Me ha gustado el estilo de la explicación y por supuesto lo que significa el diagrama de voronoi. Llegué hasta aquí investigando sobre el significado de la palabra voronoi que nombra la colección de joyas de una diseñadora madrileña Andrea Génova

RomanuelRomanuel

Excelente post… comentario de un especialista de GC hacia otro!!!! si pudieras hacer algo asi pero relacionado con el problema inverso, aunque en el final de tu post comentas algo sobre eso…. seria de mucho interes para el publico general y que normalmente piensa que nuestro trabajo es algo aburrido y tipico solo de geeks.

Saludos y continua con buenos post como este

aurelioaurelio

Encuentro muy sustancioso el contenido y muy ameno el estilo de su nota. Gracias por compartirla!
Trabajo en temas de movilidad y transporte público y ahora intuyo que con los diagramas de Voronoi se podrían reflejar perfectamente qué barrios/áreas urbanas ofrecen mayores o menores calidades de movilidad. Al respecto, debo refrescar lo que aprendí de matemáticas y seguir investigando.
Reciba un saludo cordial y nuevamente mi reconocimiento.

Ricardo Armando Martínez MagañaRicardo Armando Martínez Magaña

Dentro de los polígonos mayores, es posible trazar polígonos menores, sin menoscabo de los límites de los mayores o se modifican estos últimos? Gracias, me pareció muy útil el artículo

FernandoFernando

Hay un relación biunívoca entre las regiones y los puntos generadores que le dan origen. Si “agregaras” mas regiones implicaría nuevos puntos generadores lo que se correspondería con otro diagrama voroni

JuanmaJuanma

Magnífico artículo, a ver que les parece mañana a mis niños de segundo de eso. Seguro que lo disfrutan tanto como yo.

HdcHdc

Brillante articulo y curiosisimo!
En la industria del petroleo aplicamos esta tecnica de forma ‘pseudo-analitica’ para estudiar los régimenes difusorios e investigar cuales son los poligonos ‘drenados’.

SolomilloSolomillo

Me encanta este artículo, sencillamente te engancha.
Hace un rato que llevo mirándome la piel del dorso de las manos y efectivamente, podría ser perfectamente un diagrama de Voroni, y los pelillos parecen nacer siempre en los límites de las regiones. He de dejarlo ya, que me voy a quedar pistojo, definitivamente me bajo a los chinos a comprarme una lupa.

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>