Todos los caminos llevan a Roma... pero aún así te aconsejo mirar un mapa.

Hoy os traemos un pequeño aperitivo geométrico de la mano de los señores Delaunay y Voronoi, dos matemáticos rusos que le han hecho la vida más fácil a toda una multitud de diversos profesionales tales como arquitectos o ingenieros de caminos gracias al método que os vamos a explicar.

En resumidas cuentas, lo que hoy vamos a intentar hacer es pintar imágenes como esta:

Donde cada punto es algo que nos interesa separar y las líneas son las fronteras de la región que domina cada punto (a modo de una capital y su provincia, por ejemplo). Luego especificaremos más al respecto.

Manos a la obra. Supongamos que tenemos una empresa de transportes con varias naves repartidas por la provincia para hacer los repartos. Cada punto de la imagen siguiente va a representar una nave:

Bien, como la gasolina está cara y cada vez cuesta más ganarse el pan, supongamos que queremos delimitar bien las zonas de reparto de cada nave para viajar lo mínimo posible y así recortar costes, de manera que si una sede está más cerca del destino de un paquete que otra, el paquete debe salir de dicha nave.

Dicho de un modo un poco más formal, lo que queremos es determinar las zonas del plano que están más cercanas a cada punto.

Bien, aquí hacemos la primera parada porque uno no sabe por dónde meterle mano al problema. O aquí la hacían, mejor dicho, los que se planteaban este problema hasta que una feliz mañana de 1934 el señor Delauney puso el broche dorado al trabajo que grabaría su nombre en los libros de geometría avanzada: el Algoritmo de Delauney.

Este algoritmo, también llamado Triangulación de Delauney, consiste en, dados una serie de puntos (vértices), trazar triángulos entre dichos vértices pero atendiendo a unos pequeños detalles.

Por ejemplo, tomando como puntos los que teníamos en nuestro problema, una posible triangulación sería:

Efectivamente, esta es una posible triangulación, pero no es la que buscamos. La triangulación que buscamos debe cumplir la llamada Condición de Delauney: "Decimos que una triangulación (red de triángulos) cumple la Condición de Delauney cuando cualquier circunferencia trazada entre los tres vértices de cada triángulo no tenga ningún punto en su interior". Veamos claramente que la anterior triangulación no cumple nuestra condición con esta imagen:

Bien, ¿cómo resolvemos el problema? pues probando diversas triangulaciones (para los más perezosos o los que se planteen el problema para un número muy grande de puntos hay un método muy complicado que hace este trabajo bastante bien por nosotros pero que por razones de complejidad no está en mi mano explicarlo en este blog, al menos por ahora). En el caso que nos ocupa y con un poco de esfuerzo vemos que el traspiés se salva cambiando de lado una de las aristas:

Fijaos en que hemos cambiado un poco la red de triángulos y ya no hay ningún vértice interior en la circunferencia trazada. Si hacemos lo propio con el resto de triángulos veremos que hemos conseguido que no quede ningún vértice dentro de ninguna circunferencia y estamos en el derecho de decir que nuestra triangulación cumple la Condición de Delauney con todas las de la ley:

Bueno pues ya hemos acabado con el trabajo de nuestro amigo Delauney. Ahora es Voronoi el que tiene que ir calentando. Una vez hecha toda esta parafernalia calcularemos las regiones más cercanas a cada punto. A dichas regiones se les llama Regiones de Voronoi. Por supuesto, para ello nos apoyaremos en todo lo que hemos hecho previamente. Lo que vamos a hacer, y lo pongo en negrita para que lo leáis lentamente porque quizás suene lioso pero es bastante fácil es: Marcar el punto central de cada circunferencia y trazar perpendiculares a las aristas de los triángulos. Veamos un caso particular para dos de los círculos trazados anteriormente:

Los puntos amarillos son los centros de las circunferencias y las líneas son las perpendiculares a las aristas.

Si aplicamos el mismo método a todo el dibujo y borramos los círculos para no jalear en demasía, obtenemos lo siguiente:

Si además eliminamos la red de triángulos formada por el Algoritmo de Delauney, obtenemos las zonas que queríamos determinar:

Así, la región que está coloreada de verde en la imagen siguiente es la Región de Voronoi del punto A. Esto quiere decir que todo lo que se encuentre en la zona de verde está más cerca de A que de cualquier otro punto. Los escépticos que cojan las reglas y se pongan a medir (yo lo hice en su momento).

En resumen, las Regiones de Voronoi son las zonas del plano más cercanas a un conjunto dado de puntos. Este ingenio matemático lo usan a diario multitud de empresas en la actualidad para definir sus zonas de cobertura. Por ejemplo, tengo constancia de que McDonald's lo usa cada vez que quiere abrir un nuevo restaurante. También se utiliza en prevención de riesgos para saber qué zonas vendrían afectadas por un escape de una central nuclear, por ejemplo.

Espero que os haya gustado este ejemplo de aplicación matemática al mundo empresarial de hoy en día que comenzó como un juego geométrico y se ha hecho prácticamente imprescindible para las grandes empresas. Pronto volveremos con más curiosidades. Un saludo.