Usualmente cuando camino por la calle acostumbro jugar a pisar las lineas, o pisar bloques con un solo pie sin tocar los bordes. Es una manera un tanto infantil pero entretenida para pasar el tiempo caminando por el centro. Sin embargo, en ocasiones cuando veo caminos estrechos me gusta hacer otro juego, intento seguir un camino que equidiste de ambos lados tal como se ve en la figura de a continuación, es decir, la linea azul representa la ruta por la que camino y las lineas de los lados son bordes.

Lo que no había imaginado es que Dirichlet alrededor de 1850 se había cuestionado un problema similar el cual fue estudiado en profundidad por Voronoi después del 1900. El problema era buscar caminos entre varios puntos de tal forma que equidisten entre ellos formando una región máxima alrededor de cada punto.

En la siguiente figura se entiende mejor la idea:

Si se fijan, las lineas negras intentan pasar justo por el centro entre los puntos formando poligonos alrededor de ellos. A esto se le llama Diagrama de Voronoi.

Descubrí esto viendo aplicaciones a la rápida de la triangulación de Delaunay, la cual he ocupado para eliminar falsas rectas en búsqueda de cuadriláteros teniendo un conjunto de puntos.

Una triangulación es simplemente formar una malla de triángulos uniendo con rectas los puntos de un conjunto de puntos. La condición de Delaunay dice que no debe haber ningún punto en el interior de una circunferencia circunscrita en uno de los triángulos formados, por ejemplo el siguiente caso es correcto:

Pero el siguiente es incorrecto ya que un cuarto punto esta adentro de las circunferencias de los triángulos formados:

Esta triangulación da una solución al problema del diagrama de Voronoi, simplemente se deben unir los centros de las circunferencias de los triangulos formados, esta unión va a formar el polígono que rodea a los puntos tal como se ve en la siguiente figura:

Como ven, no es nada de otro mundo, nada espectacular, pero me parecieron entretenidos estos diagramas y por eso quise escribir sobre ellos, quizás mas adelante escriba sobre los convex hulls cuando lea mas sobre ellos, y quizás ahora al caminar me preocupe de pisar los centros de las circunferencias cuando vea algún conjunto de puntos en el suelo para variar mis juegos con los pies al caminar.