Diagrama de Voronoi

Un diagrama de Voronoi reparte el plano entre un conjunto de puntos llamados sitios: a cada sitio le corresponde la región de puntos que están al menos tan cerca de él como de cualquier otro sitio. La imagen es una ventana al plano, y el sombreado dentro de una región solo sirve para verla mejor. La sonda azul es el centro de un círculo vacío que llega hasta el sitio más cercano. Aquí puedes mover sitios y observar cómo cambian las regiones vecinas, hacer crecer cada región desde su sitio, ver la triangulación de Delaunay y distribuir los sitios de forma más uniforme hacia un panal.

Los puntos que están al menos tan cerca de un sitio $p$ como de otro sitio $q$ forman un semiplano limitado por la mediatriz de $pq$. La región de $p$ es la intersección de estos semiplanos, uno por cada otro sitio, por lo que es convexa. Solo algunas de esas mediatrices se convierten en aristas. Los sitios cuyas regiones comparten una arista con la de $p$ son sus vecinos; los demás semiplanos ya contienen toda la región. El marco solo delimita la ventana: una región se extiende hasta el infinito si y solo si su sitio está en la frontera de la envolvente convexa de todos los sitios.

Donde se encuentran tres o más regiones, el vértice está a la misma distancia de sus sitios, así que es el centro de un círculo que pasa por ellos. Dentro de ese círculo no hay ningún sitio: si lo hubiera, estaría más cerca del vértice y este pertenecería a su región. Normalmente coinciden exactamente tres regiones en un vértice. Coinciden cuatro cuando exactamente cuatro sitios están en un mismo círculo vacío, como en una cuadrícula, algo que casi nunca ocurre con sitios repartidos al azar.

Crecer hace que de cada sitio crezca un disco a la misma velocidad. Cada punto es alcanzado primero por su sitio más cercano, así que los frentes se encuentran exactamente en las aristas. La pequeña vista muestra el mismo crecimiento de lado. Sobre cada punto levanta una altura igual a la distancia al sitio más cercano: la menor altura de los conos $z = |x - s|$ situados sobre los sitios. Las crestas son las aristas y el crecimiento es el agua que sube. El último lugar inundado es el punto más alto del relieve dentro del marco: el centro del mayor círculo vacío cuyo centro está dentro del marco.

Triangulación une dos sitios cuando sus regiones comparten una arista y añade diagonales discontinuas donde cuatro o más sitios comparten un círculo vacío, como en una cuadrícula. Salvo que todos los sitios estén alineados, el resultado es la triangulación de Delaunay. La circunferencia circunscrita a cada triángulo es la del círculo vacío alrededor de un vértice del diagrama.

Uniformar lleva cada sitio al centroide de su región recortada por el marco y recalcula las regiones, ronda tras ronda. Es el algoritmo de Lloyd. El pequeño gráfico representa la distancia cuadrática media de un punto del marco al sitio más cercano, dividida por el área del marco por sitio. Ninguna ronda puede aumentarla. Con los sitios fijos, las regiones asignadas al sitio más cercano la minimizan; con las regiones fijas, lo hacen los centroides. La línea del panal es una cota inferior: el valor para hexágonos regulares iguales con los sitios en sus centros. Desde sitios dispersos, el proceso se detiene en un estado estable cercano, no en un panal perfecto. Normalmente quedan pentágonos y heptágonos unos junto a otros, como dislocaciones en un cristal.

El diagrama lleva el nombre de Gueorgui Voronoi, que estudió estas divisiones en cualquier dimensión en 1908, y la triangulación el de Boris Delaunay, que la describió en 1934.